{"id":38,"date":"2026-04-05T16:01:57","date_gmt":"2026-04-05T08:01:57","guid":{"rendered":"https:\/\/blog.sjll.top\/?p=38"},"modified":"2026-04-05T16:01:57","modified_gmt":"2026-04-05T08:01:57","slug":"%e5%bd%92%e5%b9%b6%e6%8e%92%e5%ba%8f%e7%ae%97%e6%b3%95%e8%af%a6%e8%a7%a3%ef%bc%9ac%e5%ae%9e%e7%8e%b0%e4%b8%8e%e8%bf%ad%e4%bb%a3%e7%89%88%e6%9c%ac","status":"publish","type":"post","link":"https:\/\/www.sjll.top\/index.php\/2026\/04\/05\/%e5%bd%92%e5%b9%b6%e6%8e%92%e5%ba%8f%e7%ae%97%e6%b3%95%e8%af%a6%e8%a7%a3%ef%bc%9ac%e5%ae%9e%e7%8e%b0%e4%b8%8e%e8%bf%ad%e4%bb%a3%e7%89%88%e6%9c%ac\/","title":{"rendered":"\u5f52\u5e76\u6392\u5e8f\u7b97\u6cd5\u8be6\u89e3\uff1aC++\u5b9e\u73b0\u4e0e\u8fed\u4ee3\u7248\u672c"},"content":{"rendered":"\n

\u4ec0\u4e48\u662f\u5f52\u5e76\u6392\u5e8f\uff1f<\/h2>\n\n\n\n

\u5f52\u5e76\u6392\u5e8f\uff08Merge Sort\uff09<\/strong> \u662f\u4e00\u79cd\u57fa\u4e8e\u5206\u6cbb\u601d\u60f3\u7684\u7a33\u5b9a\u6392\u5e8f\u7b97\u6cd5\uff0c\u7531John von Neumann\u4e8e1945\u5e74\u63d0\u51fa\u3002\u5b83\u5c06\u6570\u7ec4\u9012\u5f52\u5730\u5206\u6210\u4e24\u534a\u5206\u522b\u6392\u5e8f\uff0c\u7136\u540e\u518d\u5408\u5e76\u8d77\u6765\u3002\u5f52\u5e76\u6392\u5e8f\u7684\u6700\u5927\u7279\u70b9\u662f\u7a33\u5b9a\u6027<\/strong>\u2014\u2014\u76f8\u7b49\u5143\u7d20\u7684\u76f8\u5bf9\u987a\u5e8f\u5728\u6392\u5e8f\u540e\u4fdd\u6301\u4e0d\u53d8\u3002<\/p>\n\n\n\n

\u5f52\u5e76\u6392\u5e8f\u7684\u6838\u5fc3\u601d\u60f3<\/h3>\n\n\n\n
  1. \u5206\u89e3\uff08Divide\uff09<\/strong>\uff1a\u5c06\u6570\u7ec4\u4ece\u4e2d\u95f4\u5206\u6210\u4e24\u4e2a\u5b50\u6570\u7ec4<\/li>
  2. \u9012\u5f52\u6392\u5e8f\uff08Conquer\uff09<\/strong>\uff1a\u9012\u5f52\u5730\u5bf9\u4e24\u4e2a\u5b50\u6570\u7ec4\u8fdb\u884c\u5f52\u5e76\u6392\u5e8f<\/li>
  3. \u5408\u5e76\uff08Merge\uff09<\/strong>\uff1a\u5c06\u4e24\u4e2a\u6709\u5e8f\u7684\u5b50\u6570\u7ec4\u5408\u5e76\u6210\u4e00\u4e2a\u6709\u5e8f\u6570\u7ec4<\/li><\/ol>\n\n\n\n

    C++ \u4ee3\u7801\u5b9e\u73b0<\/h3>\n\n\n\n
    #include <iostream>\n#include <vector>\nusing namespace std;\n\n\/\/ \u5408\u5e76\u4e24\u4e2a\u6709\u5e8f\u6570\u7ec4\nvoid merge(vector<int>& arr, int left, int mid, int right) {\n    \/\/ \u521b\u5efa\u4e34\u65f6\u6570\u7ec4\n    vector<int> temp(right - left + 1);\n    \n    int i = left;      \/\/ \u5de6\u534a\u90e8\u5206\u6307\u9488\n    int j = mid + 1;   \/\/ \u53f3\u534a\u90e8\u5206\u6307\u9488\n    int k = 0;         \/\/ \u4e34\u65f6\u6570\u7ec4\u6307\u9488\n    \n    \/\/ \u5408\u5e76\u4e24\u4e2a\u6709\u5e8f\u90e8\u5206\n    while (i <= mid && j <= right) {\n        if (arr[i] <= arr[j]) {\n            temp[k++] = arr[i++];\n        } else {\n            temp[k++] = arr[j++];\n        }\n    }\n    \n    \/\/ \u590d\u5236\u5269\u4f59\u5143\u7d20\n    while (i <= mid) {\n        temp[k++] = arr[i++];\n    }\n    while (j <= right) {\n        temp[k++] = arr[j++];\n    }\n    \n    \/\/ \u5c06\u6392\u597d\u5e8f\u7684\u5143\u7d20\u590d\u5236\u56de\u539f\u6570\u7ec4\n    for (int p = 0; p < k; p++) {\n        arr[left + p] = temp[p];\n    }\n}\n\n\/\/ \u5f52\u5e76\u6392\u5e8f\u4e3b\u51fd\u6570\nvoid merge_sort(vector<int>& arr, int left, int right) {\n    if (left < right) {\n        int mid = left + (right - left) \/ 2;\n        \n        \/\/ \u9012\u5f52\u6392\u5e8f\u5de6\u53f3\u4e24\u90e8\u5206\n        merge_sort(arr, left, mid);\n        merge_sort(arr, mid + 1, right);\n        \n        \/\/ \u5408\u5e76\n        merge(arr, left, mid, right);\n    }\n}\n\n\/\/ \u539f\u5730\u5f52\u5e76\u6392\u5e8f\uff08\u8282\u7701\u7a7a\u95f4\uff0c\u4f46\u6548\u7387\u7565\u4f4e\uff09\nvoid merge_inplace(vector<int>& arr, int left, int mid, int right) {\n    int i = left, j = mid + 1;\n    while (i <= mid && j <= right) {\n        if (arr[i] <= arr[j]) {\n            i++;\n        } else {\n            \/\/ arr[i] > arr[j]\uff0c\u9700\u8981\u5c06arr[j]\u63d2\u5165\u5230\u524d\u9762\n            int temp = arr[j];\n            \/\/ \u5c06arr[i..j-1]\u5411\u540e\u79fb\u52a8\u4e00\u4f4d\n            for (int k = j; k > i; k--) {\n                arr[k] = arr[k - 1];\n            }\n            arr[i] = temp;\n            i++;\n            mid++;\n            j++;\n        }\n    }\n}\n\nint main() {\n    vector<int> arr = {38, 27, 43, 3, 9, 82, 10};\n    int n = arr.size();\n    \n    cout << \"\u6392\u5e8f\u524d: \";\n    for (int x : arr) cout << x << \" \";\n    cout << endl;\n    \n    merge_sort(arr, 0, n - 1);\n    \n    cout << \"\u6392\u5e8f\u540e: \";\n    for (int x : arr) cout << x << \" \";\n    cout << endl;\n    \n    return 0;\n}<\/code><\/pre>\n\n\n\n
    \u8fed\u4ee3\u7248\u5f52\u5e76\u6392\u5e8f<\/h3>\n\n\n\n
    \u9012\u5f52\u7248\u672c\u53ef\u80fd\u5bfc\u81f4\u6808\u6ea2\u51fa\uff0c\u8fed\u4ee3\u7248\u672c\u53ef\u4ee5\u907f\u514d\u8fd9\u4e2a\u95ee\u9898\uff1a<\/p>\n\n\n\n
    void merge_sort_iterative(vector<int>& arr) {\n    int n = arr.size();\n    \n    \/\/ \u4ece\u5b50\u6570\u7ec4\u5927\u5c0f\u4e3a1\u5f00\u59cb\uff0c\u9010\u6e10\u589e\u5927\n    for (int size = 1; size < n; size *= 2) {\n        \/\/ \u904d\u5386\u6240\u6709\u9700\u8981\u5408\u5e76\u7684\u5b50\u6570\u7ec4\u5bf9\n        for (int left = 0; left < n; left += 2 * size) {\n            int mid = min(left + size - 1, n - 1);\n            int right = min(left + 2 * size - 1, n - 1);\n            \n            if (mid < right) {\n                merge(arr, left, mid, right);\n            }\n        }\n    }\n}<\/code><\/pre>\n\n\n\n
    \u590d\u6742\u5ea6\u5206\u6790<\/h3>\n\n\n\n
    \u7279\u6027<\/th>\u590d\u6742\u5ea6<\/th><\/tr><\/thead>
    \u65f6\u95f4\u590d\u6742\u5ea6\uff08\u6700\u597d\/\u5e73\u5747\/\u6700\u574f\uff09<\/td>O(n log n)<\/td><\/tr>
    \u7a7a\u95f4\u590d\u6742\u5ea6<\/td>O(n)<\/td><\/tr>
    \u7a33\u5b9a\u6027<\/td>\u2705 \u7a33\u5b9a<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
    \u5f52\u5e76\u6392\u5e8f\u7684\u5e94\u7528\u573a\u666f<\/h3>\n\n\n\n
    1. \u5916\u90e8\u6392\u5e8f<\/strong>\uff1a\u5f53\u6570\u636e\u91cf\u592a\u5927\u65e0\u6cd5\u5168\u90e8\u52a0\u8f7d\u5230\u5185\u5b58\u65f6<\/li>
    2. \u94fe\u8868\u6392\u5e8f<\/strong>\uff1aO(n log n) \u7a33\u5b9a\u6392\u5e8f<\/li>
    3. \u9006\u5e8f\u5bf9\u8ba1\u6570<\/strong>\uff1a\u5229\u7528\u5f52\u5e76\u8fc7\u7a0b\u8ba1\u7b97\u9006\u5e8f\u5bf9<\/li>
    4. \u5e76\u884c\u6392\u5e8f<\/strong>\uff1a\u6613\u4e8e\u5e76\u884c\u5316\u5904\u7406<\/li><\/ol>\n\n\n\n
      \u603b\u7ed3<\/h3>\n\n\n\n
      \u5f52\u5e76\u6392\u5e8f\u662f\u4e00\u79cd\u7ecf\u5178\u7684\u5206\u6cbb\u7b97\u6cd5\uff0c\u5176\u7a33\u5b9a\u6027\u4f7f\u5176\u5728\u9700\u8981\u4fdd\u6301\u5143\u7d20\u76f8\u5bf9\u987a\u5e8f\u7684\u573a\u666f\u4e2d\u4e0d\u53ef\u66ff\u4ee3\u3002\u867d\u7136\u9700\u8981 O(n) \u7684\u989d\u5916\u7a7a\u95f4\uff0c\u4f46\u5176\u7a33\u5b9a\u6027\u548c\u4fdd\u8bc1\u7684 O(n log n) \u65f6\u95f4\u590d\u6742\u5ea6\u4f7f\u5176\u6210\u4e3a\u91cd\u8981\u7684\u6392\u5e8f\u7b97\u6cd5\u3002\u7406\u89e3\u5f52\u5e76\u6392\u5e8f\u5bf9\u4e8e\u5b66\u4e60\u66f4\u590d\u6742\u7684\u7b97\u6cd5\uff08\u5982\u5f52\u5e76\u6811\u3001CDQ\u5206\u6cbb\u7b49\uff09\u4e5f\u5f88\u6709\u5e2e\u52a9\u3002<\/p>\n","protected":false},"excerpt":{"rendered":"
      \u4ec0\u4e48\u662f\u5f52\u5e76\u6392\u5e8f\uff1f \u5f52\u5e76\u6392\u5e8f\uff08Merge Sort\uff09 \u662f\u4e00\u79cd\u57fa\u4e8e\u5206\u6cbb\u601d\u60f3\u7684\u7a33\u5b9a\u6392\u5e8f\u7b97\u6cd5\uff0c\u7531John von Ne […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3],"tags":[34,33,41,42,43,40,39],"class_list":["post-38","post","type-post","status-publish","format-standard","hentry","category-3","tag-conquer","tag-divide","tag-int-left","tag-int-mid","tag-int-right","tag-merge-sort","tag-c"],"_links":{"self":[{"href":"https:\/\/www.sjll.top\/index.php\/wp-json\/wp\/v2\/posts\/38","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.sjll.top\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.sjll.top\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.sjll.top\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.sjll.top\/index.php\/wp-json\/wp\/v2\/comments?post=38"}],"version-history":[{"count":1,"href":"https:\/\/www.sjll.top\/index.php\/wp-json\/wp\/v2\/posts\/38\/revisions"}],"predecessor-version":[{"id":49,"href":"https:\/\/www.sjll.top\/index.php\/wp-json\/wp\/v2\/posts\/38\/revisions\/49"}],"wp:attachment":[{"href":"https:\/\/www.sjll.top\/index.php\/wp-json\/wp\/v2\/media?parent=38"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.sjll.top\/index.php\/wp-json\/wp\/v2\/categories?post=38"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.sjll.top\/index.php\/wp-json\/wp\/v2\/tags?post=38"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}