{"id":787,"date":"2023-02-08T08:45:43","date_gmt":"2023-02-08T00:45:43","guid":{"rendered":"http:\/\/www.huangrongzhen.ink\/?p=787"},"modified":"2023-02-08T08:46:30","modified_gmt":"2023-02-08T00:46:30","slug":"%e5%bd%92%e5%b9%b6%e6%8e%92%e5%ba%8f%e7%ae%97%e6%b3%95","status":"publish","type":"post","link":"https:\/\/www.huangrongzhen.ink\/?p=787","title":{"rendered":"\u5f52\u5e76\u6392\u5e8f\u7b97\u6cd5"},"content":{"rendered":"<div class=\"wp-block-post-excerpt\"><p class=\"wp-block-post-excerpt__excerpt\">\u4f7f\u7528 C \u8bed\u8a00\u5b9e\u73b0\u5f52\u5e76\u6392\u5e8f\u7b97\u6cd5 <\/p><\/div>\n\n\n<p>\u6e90\u4ee3\u7801\u5982\u4e0b\u6240\u793a<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code lang=\"c\" class=\"language-c\">#include \"malloc.h\"\n\n\/\/\u5347\u5e8f\u6392\u5e8f\uff0cA[p]-A[q]\uff0cA[q + 1]-A[r]\u8fd9\u4e24\u90e8\u5206\u5df2\u7ecf\u6392\u5e8f\u597d\nvoid Merge(unsigned int* A, unsigned int p, unsigned int q, unsigned int r)\n{\n  unsigned int n1, n2, i, j, k;\n  unsigned int* L;\n  unsigned int* R;\n\n  \/\/\u8ba1\u7b97\u6570\u7ec41\u548c\u6570\u7ec42\u7684\u5927\u5c0f\n  n1 = q - p + 1;\n  n2 = r - q;\n\n  \/\/\u7533\u8bf7\u52a8\u6001\u5185\u5b58\n  L = malloc((n1 + 1) * sizeof(unsigned int));\n  R = malloc((n2 + 1) * sizeof(unsigned int));\n  if ((NULL == L) || (NULL == R))\n  {\n    printf(\"Merge: fail to malloc\\r\\n\");\n    while (1) {}\n  }\n\n  \/\/\u4fdd\u5b58\u7b2c\u4e00\u90e8\u5206\u6570\u636e\n  for (i = 0; i &lt; n1; i++){L[i] = A[p + i];}\n\n  \/\/\u4fdd\u5b58\u7b2c\u4e8c\u90e8\u5206\u6570\u636e\n  for (j = 0; j &lt; n2; j++){R[j] = A[q + 1 + j];}\n\n  \/\/\u8bbe\u7f6e\u54e8\u5175\n  L[n1] = 0xFFFFFFFF;\n  R[n2] = 0xFFFFFFFF;\n\n  \/\/\u6392\u5e8f\n  i = 0; j = 0;\n  for (k = p; k &lt;= r; k++)\n  {\n    if (L[i] &lt;= R[j])\n    {\n      A[k] = L[i];\n      i++;\n    }\n    else\n    {\n      A[k] = R[j];\n      j++;\n    }\n  }\n\n  \/\/\u91ca\u653e\u52a8\u6001\u5185\u5b58\n  free(L);\n  free(R);\n}\n\n\/\/\u5f52\u5e76\u6392\u5e8f\nvoid MergeSort(unsigned int* A, unsigned int p, unsigned int r)\n{\n  unsigned int q;\n  \n  if (p &lt; r)\n  {\n    q = (p + r) \/ 2;\n    MergeSort(A, p, q);\n    MergeSort(A, q + 1, r);\n    Merge(A, p, q, r);\n  }\n}\n<\/code><\/pre>\n\n\n\n<p>\u6d4b\u8bd5\u4ee3\u7801\u5982\u4e0b\u6240\u793a<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code lang=\"c\" class=\"language-c\">#include \"stdio.h\"\n#include \"malloc.h\"\n#include &lt;time.h&gt;\n\n#define TEST_LEN 64\n\nvoid main(void)\n{\n  unsigned int* a;\n  unsigned int i, data;\n\n  \/\/\u8bbe\u7f6e\u968f\u673a\u6570\u79cd\u5b50\n  srand((unsigned)time(NULL));\n\n  \/\/\u7533\u8bf7\u52a8\u6001\u5185\u5b58\n  a = malloc(TEST_LEN * sizeof(unsigned int));\n  if (NULL == a)\n  {\n    printf(\"main: fail to malloc\\r\\n\");\n    while (1) {}\n  }\n\n  \/\/\u586b\u5145\u6570\u7ec4\u91cc\u8fb9\u7684\u5185\u5bb9\n  for (i = 0; i &lt; TEST_LEN; i++)\n  {\n    do\n    {\n      data = rand() % 256;\n    } while (0xFFFFFFFF == data);\n    a[i] = data;\n  }\n\n  \/\/\u6392\u5e8f\n  MergeSort(a, 0, TEST_LEN - 1);\n\n  \/\/\u6253\u5370\n  for (i = 0; i &lt; TEST_LEN; i++)\n  {\n    printf(\"%d, \", a[i]);\n  }\n\n  \/\/\u91ca\u653e\u52a8\u6001\u5185\u5b58\n  free(a);\n\n  while (1) {}\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>\u4f7f\u7528 C \u8bed\u8a00\u5b9e\u73b0\u5f52\u5e76\u6392\u5e8f\u7b97\u6cd5<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[6],"tags":[],"_links":{"self":[{"href":"https:\/\/www.huangrongzhen.ink\/index.php?rest_route=\/wp\/v2\/posts\/787"}],"collection":[{"href":"https:\/\/www.huangrongzhen.ink\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.huangrongzhen.ink\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.huangrongzhen.ink\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.huangrongzhen.ink\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=787"}],"version-history":[{"count":2,"href":"https:\/\/www.huangrongzhen.ink\/index.php?rest_route=\/wp\/v2\/posts\/787\/revisions"}],"predecessor-version":[{"id":789,"href":"https:\/\/www.huangrongzhen.ink\/index.php?rest_route=\/wp\/v2\/posts\/787\/revisions\/789"}],"wp:attachment":[{"href":"https:\/\/www.huangrongzhen.ink\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=787"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.huangrongzhen.ink\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=787"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.huangrongzhen.ink\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=787"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}