{"id":471,"date":"2025-05-14T15:17:09","date_gmt":"2025-05-14T07:17:09","guid":{"rendered":"https:\/\/www.aqrboyblog.top\/?p=471"},"modified":"2025-05-14T15:17:10","modified_gmt":"2025-05-14T07:17:10","slug":"%e6%8e%92%e5%ba%8f%e6%96%b9%e6%b3%95","status":"publish","type":"post","link":"https:\/\/www.aqrboyblog.top\/?p=471","title":{"rendered":"\u6392\u5e8f\u65b9\u6cd5"},"content":{"rendered":"\n

1.\u63d2\u5165\u6392\u5e8f<\/h2>\n\n\n\n
void InsertSort(int* arr, int n)\n{\n\tfor (int i = 0; i < n - 1; ++i)\n\t{\n\t\t\/\/\u8bb0\u5f55\u6709\u5e8f\u5e8f\u5217\u6700\u540e\u4e00\u4e2a\u5143\u7d20\u7684\u4e0b\u6807\n\t\tint end = i;\n\t\t\/\/\u5f85\u63d2\u5165\u7684\u5143\u7d20\n\t\tint tem = arr[end + 1];\n\t\t\/\/\u5355\u8d9f\u6392\n\t\twhile (end >= 0)\n\t\t{\n\t\t\t\/\/\u6bd4\u63d2\u5165\u7684\u6570\u5927\u5c31\u5411\u540e\u79fb\n\t\t\tif (tem < arr[end])\n\t\t\t{\n\t\t\t\tarr[end + 1] = arr[end];\n\t\t\t\tend--;\n\t\t\t}\n\t\t\t\/\/\u6bd4\u63d2\u5165\u7684\u6570\u5c0f\uff0c\u8df3\u51fa\u5faa\u73af\n\t\t\telse\n\t\t\t{\n\t\t\t\tbreak;\n\t\t\t}\n\t\t}\n\t\t\/\/tem\u653e\u5230\u6bd4\u63d2\u5165\u7684\u6570\u5c0f\u7684\u6570\u7684\u540e\u9762\n\t\tarr[end  + 1] = tem;\n\t\t\/\/\u4ee3\u7801\u6267\u884c\u5230\u6b64\u4f4d\u7f6e\u6709\u4e24\u79cd\u60c5\u51b5:\n\t\t\/\/1.\u5f85\u63d2\u5165\u5143\u7d20\u627e\u5230\u5e94\u63d2\u5165\u4f4d\u7f6e\uff08break\u8df3\u51fa\u5faa\u73af\u5230\u6b64\uff09\n\t\t\/\/2.\u5f85\u63d2\u5165\u5143\u7d20\u6bd4\u5f53\u524d\u6709\u5e8f\u5e8f\u5217\u4e2d\u7684\u6240\u6709\u5143\u7d20\u90fd\u5c0f\uff08while\u5faa\u73af\u7ed3\u675f\u540e\u5230\u6b64\uff09\n\t}\n}\n<\/code><\/pre>\n\n\n\n
2.\u5e0c\u5c14\u6392\u5e8f<\/h2>\n\n\n\n
\/\/\u5e0c\u5c14\u6392\u5e8f\nvoid ShellSort(int* arr, int n)\n{\n\tint gap = n;\n\twhile (gap>1)\n\t{\n\t\t\/\/\u6bcf\u6b21\u5bf9gap\u6298\u534a\u64cd\u4f5c\n\t\tgap = gap \/ 2;\n\t\t\/\/\u5355\u8d9f\u6392\u5e8f\n\t\tfor (int i = 0; i < n - gap; ++i)\n\t\t{\n\t\t\tint end = i;\n\t\t\tint tem = arr[end + gap];\n\t\t\twhile (end >= 0)\n\t\t\t{\n\t\t\t\tif (tem < arr[end])\n\t\t\t\t{\n\t\t\t\t\tarr[end + gap] = arr[end];\n\t\t\t\t\tend -= gap;\n\t\t\t\t}\n\t\t\t\telse\n\t\t\t\t{\n\t\t\t\t\tbreak;\n\t\t\t\t}\n\t\t\t}\n\t\t\tarr[end + gap] = tem;\n\t\t}\n\t}\n}\n<\/code><\/pre>\n\n\n\n
3.\u9009\u62e9\u6392\u5e8f<\/h2>\n\n\n\n
\/\/\u9009\u62e9\u6392\u5e8f\nvoid swap(int* a, int* b)\n{\n\tint tem = *a;\n\t*a = *b;\n\t*b = tem;\n}\nvoid SelectSort(int* arr, int n)\n{\n\t\/\/\u4fdd\u5b58\u53c2\u4e0e\u5355\u8d9f\u6392\u5e8f\u7684\u7b2c\u4e00\u4e2a\u6570\u548c\u6700\u540e\u4e00\u4e2a\u6570\u7684\u4e0b\u6807\n\tint begin = 0, end = n - 1;\n\twhile (begin < end)\n\t{\n\t\t\/\/\u4fdd\u5b58\u6700\u5927\u503c\u7684\u4e0b\u6807\n\t\tint maxi = begin;\n\t\t\/\/\u4fdd\u5b58\u6700\u5c0f\u503c\u7684\u4e0b\u6807\n\t\tint mini = begin;\n\t\t\/\/\u627e\u51fa\u6700\u5927\u503c\u548c\u6700\u5c0f\u503c\u7684\u4e0b\u6807\n\t\tfor (int i = begin; i <= end; ++i)\n\t\t{\n\t\t\tif (arr[i] < arr[mini])\n\t\t\t{\n\t\t\t\tmini = i;\n\t\t\t}\n\t\t\tif (arr[i] > arr[maxi])\n\t\t\t{\n\t\t\t\tmaxi = i;\n\t\t\t}\n\t\t}\n\t\t\/\/\u6700\u5c0f\u503c\u653e\u5728\u5e8f\u5217\u5f00\u5934\n\t\tswap(&arr[mini], &arr[begin]);\n\t\t\/\/\u9632\u6b62\u6700\u5927\u7684\u6570\u5728begin\u4f4d\u7f6e\u88ab\u6362\u8d70\n\t\tif (begin == maxi)\n\t\t{\n\t\t\tmaxi = mini;\n\t\t}\n\t\t\/\/\u6700\u5927\u503c\u653e\u5728\u5e8f\u5217\u7ed3\u5c3e\n\t\tswap(&arr[maxi], &arr[end]);\n\t\t++begin;\n\t\t--end;\n\t}\n}\n<\/code><\/pre>\n\n\n\n
4.\u5192\u6ce1\u6392\u5e8f<\/h2>\n\n\n\n
\/\/\u5192\u6ce1\u6392\u5e8f\nvoid BubbleSort(int* arr, int n)\n{\n\tint end = n;\n\twhile (end)\n\t{\n\t\tint flag = 0;\n\t\tfor (int i = 1; i < end; ++i)\n\t\t{\n\t\t\tif (arr[i - 1] > arr[i])\n\t\t\t{\n\t\t\t\tint tem = arr[i];\n\t\t\t\tarr[i] = arr[i - 1];\n\t\t\t\tarr[i - 1] = tem;\n\t\t\t\tflag = 1;\n\t\t\t}\n\t\t}\n\t\tif (flag == 0)\n\t\t{\n\t\t\tbreak;\n\t\t}\n\t\t--end;\n\t}\n}\n<\/code><\/pre>\n\n\n\n
5.hoare\u7248\u672c(\u5de6\u53f3\u6307\u9488\u6cd5)<\/h2>\n\n\n\n
\/\/\u5feb\u901f\u6392\u5e8f   hoare\u7248\u672c(\u5de6\u53f3\u6307\u9488\u6cd5)\nvoid QuickSort(int* arr, int begin, int end)\n{\n\t\/\/\u53ea\u6709\u4e00\u4e2a\u6570\u6216\u533a\u95f4\u4e0d\u5b58\u5728\n\tif (begin >= end)\n\t\treturn;\n\tint left = begin;\n\tint right = end;\n\t\/\/\u9009\u5de6\u8fb9\u4e3akey\n\tint keyi = begin;\n\twhile (begin < end)\n\t{\n\t\t\/\/\u53f3\u8fb9\u9009\u5c0f   \u7b49\u53f7\u9632\u6b62\u548ckey\u503c\u76f8\u7b49    \u9632\u6b62\u987a\u5e8fbegin\u548cend\u8d8a\u754c\n\t\twhile (arr[end] >= arr[keyi] && begin < end)\n\t\t{\n\t\t\t--end;\n\t\t}\n\t\t\/\/\u5de6\u8fb9\u9009\u5927\n\t\twhile (arr[begin] <= arr[keyi] && begin < end)\n\t\t{\n\t\t\t++begin;\n\t\t}\n\t\t\/\/\u5c0f\u7684\u6362\u5230\u53f3\u8fb9\uff0c\u5927\u7684\u6362\u5230\u5de6\u8fb9\n\t\tswap(&arr[begin], &arr[end]);\n\t}\n\tswap(&arr[keyi], &arr[end]);\n\tkeyi = end;\n\t\/\/[left,keyi-1]keyi[keyi+1,right]\n\tQuickSort(arr, left, keyi - 1);\n\tQuickSort(arr,keyi + 1,right);\n}\n<\/code><\/pre>\n\n\n\n
5.2\u6316\u5751\u6cd5<\/h2>\n\n\n\n
\/\/\u5feb\u901f\u6392\u5e8f\u6cd5  \u6316\u5751\u6cd5\nvoid QuickSort1(int* arr, int begin, int end)\n{\n\tif (begin >= end)\n\t\treturn;\n\tint left = begin,right = end;\n\tint key = arr[begin];\n\twhile (begin < end)\n\t{\n\t\t\/\/\u627e\u5c0f\n\t\twhile (arr[end] >= key && begin < end)\n\t\t{\n\t\t\t--end;\n\t\t}\n\t\t\/\/\u5c0f\u7684\u653e\u5230\u5de6\u8fb9\u7684\u5751\u91cc\n\t\tarr[begin] = arr[end];\n\t\t\/\/\u627e\u5927\n\t\twhile (arr[begin] <= key && begin < end)\n\t\t{\n\t\t\t++begin;\n\t\t}\n\t\t\/\/\u5927\u7684\u653e\u5230\u53f3\u8fb9\u7684\u5751\u91cc\n\t\tarr[end] = arr[begin];\n\t}\n\tarr[begin] = key;\n\tint keyi = begin;\n\t\/\/[left,keyi-1]keyi[keyi+1,right]\n\tQuickSort1(arr, left, keyi - 1);\n\tQuickSort1(arr, keyi + 1, right);\n}\n<\/code><\/pre>\n\n\n\n
5.3\u524d\u540e\u6307\u9488\u6cd5<\/h2>\n\n\n\n
\/\/\u5feb\u901f\u6392\u5e8f\u6cd5  \u524d\u540e\u6307\u9488\u7248\u672c\nvoid QuickSort2(int* arr, int begin, int end)\n{\n\tif (begin >= end)\n\t\treturn;\n\tint cur = begin, prev = begin - 1;\n\tint keyi = end;\n\twhile (cur != keyi)\n\t{\n\t\tif (arr[cur] < arr[keyi] && ++prev != cur)\n\t\t{\n\t\t\tswap(&arr[cur], &arr[prev]);\n\t\t}\n\t\t++cur;\n\t}\n\tswap(&arr[++prev],&arr[keyi]);\n\tkeyi = prev;\n\t\/\/[begin,keyi -1]keyi[keyi+1,end]\n\tQuickSort2(arr, begin, keyi - 1);\n\tQuickSort2(arr, keyi + 1, end);\n\n}\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
1.\u63d2\u5165\u6392\u5e8f 2.\u5e0c\u5c14\u6392\u5e8f 3.\u9009\u62e9\u6392\u5e8f 4 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-471","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/www.aqrboyblog.top\/index.php?rest_route=\/wp\/v2\/posts\/471","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.aqrboyblog.top\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.aqrboyblog.top\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.aqrboyblog.top\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.aqrboyblog.top\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=471"}],"version-history":[{"count":1,"href":"https:\/\/www.aqrboyblog.top\/index.php?rest_route=\/wp\/v2\/posts\/471\/revisions"}],"predecessor-version":[{"id":472,"href":"https:\/\/www.aqrboyblog.top\/index.php?rest_route=\/wp\/v2\/posts\/471\/revisions\/472"}],"wp:attachment":[{"href":"https:\/\/www.aqrboyblog.top\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=471"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.aqrboyblog.top\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=471"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.aqrboyblog.top\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=471"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}