{"id":182,"date":"2013-06-08T21:05:32","date_gmt":"2013-06-08T13:05:32","guid":{"rendered":"http:\/\/coderbee.net\/?p=182"},"modified":"2014-11-28T20:32:52","modified_gmt":"2014-11-28T12:32:52","slug":"%e5%90%88%e5%b9%b6%e6%8e%92%e5%ba%8f","status":"publish","type":"post","link":"https:\/\/coderbee.net\/index.php\/algorithm\/20130608\/182","title":{"rendered":"\u5408\u5e76\u6392\u5e8f"},"content":{"rendered":"<h2>\u5408\u5e76\u6392\u5e8f<\/h2>\n<p>\u5408\u5e76\u6392\u5e8f\u662f\u57fa\u4e8e\u5206\u6cbb\u601d\u60f3\u7684\uff1a<br \/>\n1.  \u5982\u679c\u6570\u7ec4\u8db3\u591f\u5c0f\uff0c\u76f4\u63a5\u5bf9\u6570\u7ec4\u8fdb\u884c\u6392\u5e8f\u3002<br \/>\n2.  \u5426\u5219\uff0c\u628a\u6570\u7ec4\u5212\u5206\u4e3a\u4e24\u4e2a\u5b50\u6570\u7ec4\uff0c\u5206\u522b\u8fdb\u884c\u5408\u5e76\u6392\u5e8f\uff0c\u7136\u540e\u5408\u5e76\u4e24\u4e2a\u6709\u5e8f\u7684\u5b50\u6570\u7ec4\u4e3a\u6709\u5e8f\u6570\u7ec4\u3002<\/p>\n<p>\u8fdb\u884c\u5408\u5e76\u64cd\u4f5c\u7684\u590d\u6742\u5ea6\u4e3aO(n)\uff0c\u7531\u4e8e\u6bcf\u6b21\u628a\u6570\u7ec4\u5206\u4e3a2\u4e2a\u5b50\u6570\u7ec4\uff0c\u9700\u8981\u8fdb\u884clg(n)\u6b21\u5408\u5e76\uff0c\u6240\u4ee5\u65f6\u95f4\u590d\u6742\u5ea6\u4e3aO(n*lg(n))\uff0c\u3002<\/p>\n<p>\u6bcf\u6b21\u5408\u5e76\u90fd\u9700\u8981\u4e0e\u4e24\u4e2a\u5b50\u6570\u7ec4\u957f\u5ea6\u548c \u5927\u5c0f\u7684\u6570\u7ec4\uff0c\u6240\u4ee5\u7a7a\u95f4\u590d\u6742\u5ea6\u4e3aO(n)\u3002<\/p>\n<p><!--more--><\/p>\n<h3>\u5b9e\u73b0<\/h3>\n<pre><code language=\"go\">\nfunc MergeSort(arr []int) []int {\n    length := len(arr)\n    if length < 2 {\n        return arr\n    }\n\n    mid := length >> 1\n    \/\/mid := length \/ 2\n    larr := MergeSort(arr[0:mid])\n    rarr := MergeSort(arr[mid:length])\n\n    return merge(larr, rarr, asc)\n}\n\nfunc merge(larr []int, rarr []int, compare func(int, int) bool) []int {\n    lLen, rLen := len(larr), len(rarr)\n    arr := make([]int, lLen+rLen)\n\n    l, r, i := 0, 0, 0\n    for ; l < lLen &#038;&#038; r < rLen; i++ {\n        if compare(larr[l], rarr[r]) {\n            arr[i] = rarr[r]\n            r++\n        } else {\n            arr[i] = larr[l]\n            l++\n        }\n    }\n\n    if l >= lLen {\n        util.ArrayCopy(rarr, r, arr, i, rLen-r)\n    } else {\n        util.ArrayCopy(larr, l, arr, i, lLen-l)\n    }\n\n    return arr\n}\n\nfunc asc(l int, r int) bool {\n    return l > r\n}\n<\/code><\/pre>\n<hr\/>\n<p>\u6b22\u8fce\u5173\u6ce8\u6211\u7684\u5fae\u4fe1\u516c\u4f17\u53f7: <strong>coderbee\u7b14\u8bb0<\/strong>\uff0c\u53ef\u4ee5\u66f4\u53ca\u65f6\u56de\u590d\u4f60\u7684\u8ba8\u8bba\u3002<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" width=\"258\" height=\"258\" src=\"https:\/\/coderbee.net\/wp-content\/uploads\/2019\/01\/coderbee-note.jpg\" class=\"alignnone size-full wp-image-1707\"><\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u5408\u5e76\u6392\u5e8f \u5408\u5e76\u6392\u5e8f\u662f\u57fa\u4e8e\u5206\u6cbb\u601d\u60f3\u7684\uff1a 1. \u5982\u679c\u6570\u7ec4\u8db3\u591f\u5c0f\uff0c\u76f4\u63a5\u5bf9\u6570\u7ec4\u8fdb\u884c\u6392\u5e8f\u3002 &hellip; <a href=\"https:\/\/coderbee.net\/index.php\/algorithm\/20130608\/182\">\u7ee7\u7eed\u9605\u8bfb <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[53],"tags":[55,56],"_links":{"self":[{"href":"https:\/\/coderbee.net\/index.php\/wp-json\/wp\/v2\/posts\/182"}],"collection":[{"href":"https:\/\/coderbee.net\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/coderbee.net\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/coderbee.net\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/coderbee.net\/index.php\/wp-json\/wp\/v2\/comments?post=182"}],"version-history":[{"count":9,"href":"https:\/\/coderbee.net\/index.php\/wp-json\/wp\/v2\/posts\/182\/revisions"}],"predecessor-version":[{"id":1114,"href":"https:\/\/coderbee.net\/index.php\/wp-json\/wp\/v2\/posts\/182\/revisions\/1114"}],"wp:attachment":[{"href":"https:\/\/coderbee.net\/index.php\/wp-json\/wp\/v2\/media?parent=182"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/coderbee.net\/index.php\/wp-json\/wp\/v2\/categories?post=182"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/coderbee.net\/index.php\/wp-json\/wp\/v2\/tags?post=182"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}