{"id":262,"date":"2021-07-20T21:10:42","date_gmt":"2021-07-20T13:10:42","guid":{"rendered":"https:\/\/blog.cauchyschwarz.com\/?p=262"},"modified":"2021-07-20T21:10:44","modified_gmt":"2021-07-20T13:10:44","slug":"%e5%bf%ab%e9%80%9f%e6%8e%92%e5%ba%8f","status":"publish","type":"post","link":"https:\/\/blog.cauchyschwarz.com\/?p=262","title":{"rendered":"\u5feb\u901f\u6392\u5e8f"},"content":{"rendered":"\n<pre class=\"wp-block-code\"><code>#include &lt;stdio.h>\n#include &lt;stdlib.h>\n#include &lt;time.h>\n\nint cmp(const void *pa, const void *pb) {\n    return *(int*)pa - *(int*)pb;\n}\n\nvoid printArr(int a&#91;], int size) {\n    for (int i = 0; i &lt; size; i++) {\n        printf(\"%d \", a&#91;i]);\n    }\n    printf(\"\\n\");\n}\n\nvoid swap(int arr&#91;], int a, int b) {\n    int tmp = arr&#91;a];\n    arr&#91;a] = arr&#91;b];\n    arr&#91;b] = tmp;\n}\n\nvoid qsortKR(int arr&#91;], int left, int right) {\n    if (left >= right) {\n        return;\n    }\n    int last = left;\n    swap(arr, left, (left+right)\/2);\n    for (int i = left+1; i &lt; right; i++) {\n        if (arr&#91;i] &lt; arr&#91;left]) {\n            swap(arr, i, ++last);\n        }\n    }\n    swap(arr, left, last);\n    qsortKR(arr, left, last);\n    qsortKR(arr, last+1, right);\n}\n\nint main(int argc, char **argv)\n{\n    printf(\"%ld\\n\", sizeof(int));\n    int num = atoi(argv&#91;1]);\n    int *arr = (int*)malloc(sizeof(int) * num);\n    int *arr2 = (int*)malloc(sizeof(int) * num);\n    for (int i = 0; i &lt; num; i++) {\n        arr&#91;i] = rand();\n        arr2&#91;i] = arr&#91;i];\n    }\n\n    clock_t start1 = clock();\n    qsort(arr, num, sizeof(int), cmp);\n    clock_t start2 = clock();\n    \/\/printArr(arr, num);\n\n    clock_t start3 = clock();\n    qsortKR(arr2, 0, num);\n    clock_t start4 = clock();\n    \/\/printArr(arr2, num);\n    \n    for(int i = 0; i &lt; num; i++) {\n        if (arr&#91;i] != arr2&#91;i]) {\n            printf(\"error!\\n\");\n            break;\n        }\n    }\n\n    printf(\"stdlib %lf qsortKR %lf\\n\", (start2-start1)*1.0\/CLOCKS_PER_SEC, (start4-start3)*1.0\/CLOCKS_PER_SEC);\n\n    return 0;\n}\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[10],"tags":[26],"class_list":["post-262","post","type-post","status-publish","format-standard","hentry","category-10","tag-algorithm"],"_links":{"self":[{"href":"https:\/\/blog.cauchyschwarz.com\/index.php?rest_route=\/wp\/v2\/posts\/262","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.cauchyschwarz.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.cauchyschwarz.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.cauchyschwarz.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.cauchyschwarz.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=262"}],"version-history":[{"count":1,"href":"https:\/\/blog.cauchyschwarz.com\/index.php?rest_route=\/wp\/v2\/posts\/262\/revisions"}],"predecessor-version":[{"id":263,"href":"https:\/\/blog.cauchyschwarz.com\/index.php?rest_route=\/wp\/v2\/posts\/262\/revisions\/263"}],"wp:attachment":[{"href":"https:\/\/blog.cauchyschwarz.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=262"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.cauchyschwarz.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=262"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.cauchyschwarz.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=262"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}