{"id":298,"date":"2011-11-16T13:59:12","date_gmt":"2011-11-16T05:59:12","guid":{"rendered":"http:\/\/wangkaixuan.tech\/?p=298"},"modified":"2020-06-06T14:01:16","modified_gmt":"2020-06-06T06:01:16","slug":"%e6%95%b0%e6%8d%ae%e7%bb%93%e6%9e%84_%e5%86%85%e9%83%a8%e6%8e%92%e5%ba%8f_%e9%93%be%e5%bc%8f%e5%9f%ba%e6%95%b0%e6%8e%92%e5%ba%8f","status":"publish","type":"post","link":"http:\/\/www.wangkaixuan.tech\/?p=298","title":{"rendered":"\u6570\u636e\u7ed3\u6784_\u5185\u90e8\u6392\u5e8f_\u94fe\u5f0f\u57fa\u6570\u6392\u5e8f"},"content":{"rendered":"\n

\u6ca1\u505a\u8fd9\u4e2a\u7b97\u6cd5\u4e4b\u524d\u89c9\u5f97\u9759\u6001\u94fe\u8868\u6ca1\u4ec0\u4e48\u7528\uff0c\u5199\u4e86\u8fd9\u4e2a\u7b97\u6cd5\u624d\u53d1\u73b0\u539f\u6765\u9759\u6001\u94fe\u8868\u662f\u5982\u6b64\u7684\u5de7\u5999\uff0c\u624d\u53d1\u73b0\u4e4b\u524d\u7684\u770b\u6cd5\u662f\u591a\u4e48\u7684\u6d45\u8584\u65e0\u77e5\uff0c\u770b\u6765\u4ee5\u540e\u8fd8\u8981\u66f4\u865a\u5fc3\u4e86\uff0c\u563f\u563f\u2026<\/p>\n\n\n\n


\u57fa\u6570\u6392\u5e8f\uff0c\u5173\u952e\u662f\u4e24\u4e2a\u8fc7\u7a0b\uff0c\u5206\u914d\u548c\u56de\u6536\uff0c\u5206\u914d\u662f\u6309\u5173\u952e\u5b57\u987a\u5e8f\u5c06\u8bb0\u5f55\u8fdb\u884c\u5206\u7c7b\u4e3a\uff0c\u56de\u6536\u662f\u5c06\u5206\u914d\u8fc7\u7a0b\u4e2d\u987a\u5e8f\u6253\u4e71\u7684\u8bb0\u5f55\u91cd\u65b0\u94fe\u63a5\u6210\u9759\u6001\u94fe\u8868\u3002\u8fd9\u6837\u4ece\u6309\u4e00\u5b9a\u987a\u5e8f\u5bf9\u5173\u952e\u5b57\u8fdb\u884c\u5206\u914d\u548c\u56de\u6536\u5230\u6700\u540e\u5c31\u80fd\u5f97\u5230\u4e00\u4e2a\u6709\u5e8f\u5e8f\u5217\u3002\u5373\u4e3a\u57fa\u6570\u6392\u5e8f\u539f\u7406\u3002<\/p>\n\n\n\n

RadixSort.h<\/p>\n\n\n\n


<\/p>\n\n\n\n

#define MAX_NUM_OF_KEY 8\n#define Radix 10\n#define MAX_SPACE 10000\n\ntypedef int KeyType;\n\ntypedef struct SLCell\n{\n\tKeyType keys[MAX_NUM_OF_KEY];\n\tint next;\n\tSLCell()\n\t{\n\t\tfor (int i = 0; i < MAX_NUM_OF_KEY; i++)\n\t\t\tkeys[i] = 0;\n\t\tnext = 0;\n\t}\n} SLCell;\n\ntypedef struct SLList\n{\n\tSLCell r[MAX_SPACE];\n\tint keynum;\n\tint recnum;\n\tSLList()\n\t{\n\t\tkeynum = 0;\n\t\trecnum = 0;\n\t}\n} SLList;\n\ntypedef int ArrType[Radix];\n\nvoid PrintSSList(const SLList &L) \/\/\u8f93\u51fa\u9759\u6001\u94fe\u8868\n{\n\tfor (int i = L.r[0].next; i != 0; i = L.r[i].next)\n\t{\n\t\tint j = L.keynum - 1;\n\t\twhile (L.r[i].keys[j] == 0 && j > 0)\n\t\t\tj--;\n\t\tif (j == 0)\n\t\t\tcout << 0;\n\t\telse\n\t\t{\n\t\t\twhile (j >= 0)\n\t\t\t\tcout << L.r[i].keys[j--];\n\t\t}\n\t\tcout << \" \";\n\t}\n\tcout << endl;\n}\n\nvoid GetRandomNum(SLList &L, int nnum, int base)\n\/\/\u5f97\u5230nnum\u4e2a\u57281...base\u4e4b\u95f4\u7684\u968f\u673a\u6570\n{\n\tsrand((unsigned) time(NULL));\n\tint num = base, t;\n\twhile (num != 0) \/\/\u5f97\u5230\u5173\u952e\u5b57\u4e2a\u6570\n\t{\n\t\tL.keynum++;\n\t\tnum \/= Radix;\n\t}\n\tfor (int i = 1; i <= nnum; i++)\n\t{\n\t\tnum = rand() % base + 1;\n\t\tt = 0;\n\t\twhile (num != 0) \/\/\u5206\u914d\u5173\u952e\u5b57\n\t\t{\n\t\t\tL.r[i].keys[t++] = num % Radix;\n\t\t\tnum \/= Radix;\n\t\t}\n\t\tL.recnum++; \/\/\u9759\u6001\u94fe\u8868\u957f\u5ea6\u589e\u4e00\n\t}\n\tfor (int i = 0; i < L.recnum; i++) \/\/\u94fe\u63a5\u9759\u6001\u94fe\u8868\n\t\tL.r[i].next = i + 1;\n}\n\nvoid Distribute(SLCell *r, int i, ArrType &f, ArrType &e)\n\/\/\u6309\u7b2ci\u4e2a\u5173\u952e\u5b57\u5206\u914d\u8bb0\u5f55\n{\n\tfor (int i = 0; i < Radix; i++)\n\t\tf[i] = 0;\n\tint p, j;\n\tfor (p = r[0].next; p != 0; p = r[p].next)\n\t{\n\t\tj = r[p].keys[i];\n\t\tif (f[j] == 0)\n\t\t\tf[j] = p;\n\t\telse\n\t\t\tr[e[j]].next = p;\n\t\te[j] = p;\n\t}\n}\n\nvoid Collect(SLCell *r, ArrType &f, ArrType &e)\n\/\/\u56de\u6536\u8bb0\u5f55\n{\n\tint j;\n\tfor (j = 0; f[j] == 0; j++)\n\t\t;\n\tr[0].next = f[j];\n\tint t = e[j];\n\twhile (j < Radix)\n\t{\n\t\tfor (j++; j < Radix && f[j] == 0; j++)\n\t\t\t;\n\t\tif (j < Radix && f[j] != 0)\n\t\t{\n\t\t\tr[t].next = f[j];\n\t\t\tt = e[j];\n\t\t}\n\t}\n\tr[t].next = 0;\n}\n\nvoid RadixSort(SLList &L) \/\/\u57fa\u6570\u6392\u5e8f\n{\n\tArrType f, e;\n\tfor (int i = 0; i < L.keynum; i++)\n\t{\n\t\tDistribute(L.r, i, f, e);\n\t\tCollect(L.r, f, e);\n\t}\n}\n<\/code><\/pre>\n\n\n\n
main.cpp<\/p>\n\n\n\n
#include<ctime>\n#include<iostream>\nusing namespace std;\n \n#include\"RadixSort.h\"\n \nint main()\n{\n\tSLList L;\/\/\u5b9a\u4e49\u9759\u6001\u94fe\u8868\n\tGetRandomNum(L,10,100);\/\/\u5f97\u5230\u968f\u673a\u6570\n\tPrintSSList(L);\/\/\u8f93\u51fa\n\tRadixSort(L);\/\/\u57fa\u6570\u6392\u5e8f\n\tPrintSSList(L);\/\/\u8f93\u51fa\n\tsystem(\"pause\");\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
\u6ca1\u505a\u8fd9\u4e2a\u7b97\u6cd5\u4e4b\u524d\u89c9\u5f97\u9759\u6001\u94fe\u8868\u6ca1\u4ec0\u4e48\u7528\uff0c\u5199\u4e86\u8fd9\u4e2a\u7b97\u6cd5\u624d\u53d1\u73b0\u539f\u6765\u9759\u6001\u94fe\u8868\u662f\u5982\u6b64\u7684\u5de7\u5999\uff0c\u624d\u53d1\u73b0\u4e4b\u524d\u7684\u770b\u6cd5\u662f\u591a\u4e48\u7684\u6d45\u8584\u65e0\u77e5\uff0c\u770b\u6765\u4ee5\u540e\u8fd8\u8981\u66f4\u865a\u5fc3\u4e86\uff0c\u563f\u563f\u2026 \u57fa\u6570\u6392\u5e8f\uff0c\u5173\u952e…<\/p>\n
 Read More  Read More<\/span><\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[9],"tags":[],"class_list":["post-298","post","type-post","status-publish","format-standard","hentry","category-06-02-"],"_links":{"self":[{"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/posts\/298","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=298"}],"version-history":[{"count":0,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/posts\/298\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=298"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=298"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=298"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}