{"id":234,"date":"2023-12-15T16:03:57","date_gmt":"2023-12-15T08:03:57","guid":{"rendered":"http:\/\/www.zhang-junyi.com\/?p=234"},"modified":"2023-12-15T16:32:11","modified_gmt":"2023-12-15T08:32:11","slug":"%e6%8e%92%e5%ba%8f%e5%ad%90%e7%b3%bb%e7%bb%9f","status":"publish","type":"post","link":"https:\/\/www.zhang-junyi.com\/?p=234","title":{"rendered":"\u6392\u5e8f\u5b50\u7cfb\u7edf"},"content":{"rendered":"\n
#include<stdio.h>\n#include<stdlib.h>\n#define MAXSIZE 100\ntypedef int KeyType;\ntypedef struct\n{   KeyType Key;\n}LineList;\n\nvoid InsertSort(LineList r[],int n)\n{\n    int i,j;\n    for(i = 2;i <= n;i++)\n    {\n        r[0] = r[i];\n        j = i-1;\n        while(r[0].Key < r[j].Key)\n        {\n            r[j+1] = r[j];\n            j = j-1;\n        }\n        r[j+1] = r[0];\n    }\n}\n\nvoid ShellSort(LineList r[],int n)\n{\n    int i,j,d;\n    d = n\/2;\n    while(d>0)\n    {   for(i = d;i <= n;i++)\n        {\n            r[0] = r[i];\n                j = j - d;\n            while(j >= 0 && r[0].Key < r[j].Key)\n            {\n                r[j+d] = r[j];\n                j = j - d;\n            }\n            r[j + d] = r[0];\n            j = j - d;\n        }\n        d = d\/2;\n    }\n}\n\nvoid BubbleSort(LineList r[],int n)\n{\n    int i,j,exchange;\n    LineList temp;\n    for(i = 1;i < n;i++)\n    {   exchange = 0;\n        for(j = 1;j <= n-i;j++)\n        if(r[j].Key > r[j+1].Key)\n        {   temp = r[j];\n            r[j] = r[j+1];\n            r[j+1] = temp;\n            exchange = 1;\n        }\n        if(exchange == 0) return;\n    }\n}\n\nvoid QuickSort(LineList r[],int first,int end)\n{\n    int i,j;\n    LineList temp;\n    i = first;j = end;temp = r[i];\n    while (i < j)\n    {\n        while(i < j && temp.Key <= r[j].Key) j--;\n            r[i] = r[j];\n        while(i < j && r[i].Key <= temp.Key) i++;\n            r[j] = r[i];\n    }\n    r[i] = temp;\n    if(first < i-1) QuickSort(r,first,i-1);\n    if(i+1 < end) QuickSort(r,i+1,end);\n}\n\nvoid SelectSort(LineList r[],int n)\n{\n    int i,j,k;\n    LineList x;\n    for(i = 1;i <= n;i++)\n    {   k = i;\n        for(j = i+1;j <= n; ++j)\n        if(r[j].Key < r[k].Key)\n            k = j;\n        if(k != j)\n        {x = r[i];r[i] = r[k];r[k] = x;}\n    }\n}\n\nvoid Sift(LineList r[],int low,int high)\n{\n    int i = low,j = 2*i;\n    LineList tmp = r[i];\n    while (j <= high)\n    {\n        if(j < high && r[j].Key < r[j+1].Key)\n            j = j + 1;\n        if(tmp.Key < r[j].Key)\n        {\n            r[i] = r[j];\n            i = j;\n            j = 2*i; \n        }\n        else break;\n    }\n    r[i] = tmp;\n}\n\nvoid HeapSort(LineList r[],int n)\n{\n    int i;\n    LineList tmp;\n    for ( i = n\/2; i >= 1; i--)\n        Sift(r,i,n);\n    for ( i = n; i >= 1; i--)\n    {\n        tmp = r[1];\n        r[1] = r[i];\n        r[i] = tmp;\n        Sift(r,1,i-1);\n    }\n}\n\nvoid Merge(LineList r[],int low,int mid,int high)\n{\n    LineList *r1;\n    int i = low,j = mid+1,k = 1;\n    r1 =(LineList *)malloc((high - low + 1)*sizeof(LineList));\n    while(i <= mid && j <= high)\n        if(r[i].Key <= r[j].Key)\n            r1[k++] = r[i++];\n        else\n            r1[k++] = r[j++];\n    while(i <= mid)\n            r1[k++] = r[i++];\n    while(j <= high)\n            r1[k++] = r[j++];\n    for(k = 1,i = low;i <= high;k++,i++)\n            r[i] = r[k];\n}\n\nvoid MergePass(LineList r[],int length,int n)\n{\n    int i;\n    for(i = 1;i+2*length-1<=n;i=i+2*length)\n        Merge(r,i,i+length-1,n);\n    if(i + length - 1 <= n)\n        Merge(r,i,i+length-1,n);\n}\n\nvoid MergeSort(LineList r[],int n)\n{\n    int length;\n    for(length = 1;length <= n;length = 2*length)\n        MergePass(r,length,n);\n}\n\nvoid OutList(LineList r[],int n)\n{\n    int i;\n    printf(\"\u6392\u5e8f\u540e\u7684\u8bb0\u5f55\u4e3a\uff1a\");\n    for (i = 1; i <= n; i++)\n        printf(\"%5d\",r[i]);\n}\n\nvoid MenuSort()\n{\n    printf(\"\\n                   \u6392\u5e8f\u5b50\u7cfb\u7edf\");\n    printf(\"\\n =================================================\");\n    printf(\"\\n|               1\u2014\u2014\u66f4\u65b0\u6392\u5e8f\u6570\u636e                    |\");\n    printf(\"\\n|               2\u2014\u2014\u76f4\u63a5\u63d2\u5165\u6392\u5e8f                    |\");\n    printf(\"\\n|               3\u2014\u2014\u5e0c\u5c14\u6392\u5e8f                        |\");\n    printf(\"\\n|               4\u2014\u2014\u5192\u6ce1\u6392\u5e8f                        |\");\n    printf(\"\\n|               5\u2014\u2014\u5feb\u901f\u6392\u5e8f                        |\");\n    printf(\"\\n|               6\u2014\u2014\u76f4\u63a5\u9009\u62e9\u6392\u5e8f                    |\");\n    printf(\"\\n|               7\u2014\u2014\u5806\u6392\u5e8f                          |\");\n    printf(\"\\n|               8\u2014\u2014\u5f52\u5e76\u6392\u5e8f                        |\");\n    printf(\"\\n|               0\u2014\u2014\u8fd4\u56de                            |\");\n    printf(\"\\n =================================================\");\n    printf(\"\\n\u8bf7\u8f93\u5165\u83dc\u5355\u53f7\uff080-8\uff09:\"); \n}\n\nint main()\n{\n    int i,n;\n    LineList r[MAXSIZE];\n    char ch1,ch2,a;\n    ch1 = 'y';\n    while (ch1 == 'y' || ch1 == 'Y')\n    {   MenuSort();\n        scanf(\"%c\",&ch2);\n        getchar();\n        switch(ch2)\n        {\n            case '1':\n                printf(\"\u8bf7\u8f93\u5165\u5f85\u6392\u5e8f\u8868\u7684\u957f\u5ea6\uff1a\");\n                scanf(\"%d\",&n);\n                printf(\"\u8bf7\u8f93\u5165%d\u4e2a\u6574\u6570\uff1a\",n);\n                for ( i = 1; i <= n; i++)\n                    scanf(\"%d\",&r[i]);\n                OutList(r,n);\n                break;\n            case '2':\n                InsertSort(r,n);\n                printf(\"\u8fdb\u884c\u76f4\u63a5\u63d2\u5165\u6392\u5e8f\uff0c\");\n                OutList(r,n);\n                break;\n            case '3':\n                ShellSort(r,n);\n                printf(\"\u8fdb\u884c\u5e0c\u5c14\u63d2\u5165\u6392\u5e8f\uff0c\");\n                OutList(r,n);\n                break;\n            case '4':\n                BubbleSort(r,n);\n                printf(\"\u8fdb\u884c\u5192\u6ce1\u6392\u5e8f\uff0c\");\n                OutList(r,n);\n                break;\n            case '5':\n                QuickSort(r,1,n);\n                printf(\"\u8fdb\u884c\u5feb\u901f\u6392\u5e8f\uff0c\");\n                OutList(r,n);\n                break;\n            case '6':\n                SelectSort(r,n);\n                printf(\"\u8fdb\u884c\u76f4\u63a5\u9009\u62e9\u6392\u5e8f\uff0c\");\n                OutList(r,n);\n                break;\n            case '7':\n                HeapSort(r,n);\n                printf(\"\u8fdb\u884c\u5806\u6392\u5e8f\uff0c\");\n                OutList(r,n);\n                break;\n            case '8':\n                MergeSort(r,n);\n                printf(\"\u8fdb\u884c\u5f52\u5e76\u6392\u5e8f\uff0c\");\n                OutList(r,n);\n                break;\n            case '0':\n                ch1 = 'n';\n                break;\n            default:\n                printf(\"\u8f93\u5165\u6709\u8bef\uff0c\u8bf7\u8f93\u51650-9\u8fdb\u884c\u9009\u62e9!\");\n        }\n        if(ch2 != '0')\n        {   printf(\"\\n\u6309\u56de\u8f66\u952e\u7ee7\u7eed\uff0c\u6309\u4efb\u610f\u952e\u8fd4\u56de\u4e3b\u83dc\u5355\uff01\\n\");\n            a = getchar();\n            if(a != '\\xA')\n            {\n                getchar();ch1 = 'n';\n            }\n        }       \n    }\n    \n}<\/code><\/pre>\n\n\n\n
\u5b9e\u9a8c9\u6392\u5e8f\u5b50\u7cfb\u7edf<\/p>\n\n\n\n
1.\u5b9e\u9a8c\u76ee\u7684<\/p>\n\n\n\n
(1)\u638c\u63e1\u5e38\u7528\u7684\u6392\u5e8f\u65b9\u6cd5\u7684\u57fa\u672c\u601d\u60f3\u3002<\/p>\n\n\n\n
(2)\u901a\u8fc7\u5b9e\u9a8c\u52a0\u6df1\u5bf9\u5404\u79cd\u7b97\u6cd5\u7684\u7406\u89e3\u3002<\/p>\n\n\n\n
(3)\u638c\u63e1\u5404\u79cd\u7b97\u6cd5\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u3002<\/p>\n\n\n\n
2.\u5b9e\u9a8c\u5185\u5bb9<\/p>\n\n\n\n
(1)\u7f16\u5199\u76f4\u63a5\u63d2\u5165\u6392\u5e8f\u3001\u5e0c\u5c14\u6392\u5e8f\u3001\u5192\u6ce1\u6392\u5e8f\u3001\u5feb\u901f\u6392\u5e8f\u3001\u9009\u62e9\u6392\u5e8f\u3001\u5f52\u5e76\u6392\u5e8f\u3001\u5806\u6392\u5e8f\u7684\u7b97\u6cd5<\/p>\n\n\n\n
\uff082)\u7a0b\u5e8f\u6267\u884c\u65f6\uff0c\u80fd\u663e\u793a\u6bcf\u4e00\u8d9f\u6392\u5e8f\u7684\u7ed3\u679c\u3002<\/p>\n\n\n\n
\uff083)\u8bbe\u8ba1\u5982\u4e0b\u9009\u62e9\u5f0f\u83dc\u5355\uff0c\u4ee5\u9009\u62e9\u83dc\u5355\u65b9\u5f0f\u8fdb\u884c\u64cd\u4f5c\u3002\u5c06\u4e0a\u8ff0\u5404\u79cd\u7b97\u6cd5\u5b9e\u73b0\u3002<\/p>\n","protected":false},"excerpt":{"rendered":"
\u5b9e\u9a8c9\u6392\u5e8f\u5b50\u7cfb\u7edf 1.\u5b9e\u9a8c\u76ee\u7684 (1)\u638c\u63e1\u5e38\u7528\u7684\u6392\u5e8f\u65b9\u6cd5\u7684\u57fa\u672c\u601d\u60f3\u3002 (2)\u901a\u8fc7\u5b9e\u9a8c\u52a0\u6df1\u5bf9\u5404\u79cd\u7b97\u6cd5\u7684\u7406\u89e3\u3002 ( […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_eb_attr":"","footnotes":""},"categories":[1],"tags":[],"class_list":["post-234","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/www.zhang-junyi.com\/index.php?rest_route=\/wp\/v2\/posts\/234","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.zhang-junyi.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.zhang-junyi.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.zhang-junyi.com\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.zhang-junyi.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=234"}],"version-history":[{"count":3,"href":"https:\/\/www.zhang-junyi.com\/index.php?rest_route=\/wp\/v2\/posts\/234\/revisions"}],"predecessor-version":[{"id":238,"href":"https:\/\/www.zhang-junyi.com\/index.php?rest_route=\/wp\/v2\/posts\/234\/revisions\/238"}],"wp:attachment":[{"href":"https:\/\/www.zhang-junyi.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=234"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.zhang-junyi.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=234"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.zhang-junyi.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=234"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}