數據結構，基數排序的過程，就是將最低位優先法用於單關鍵字的情況。基數排序的基本思想、排序的實例模擬、排序的算法等。
基本介紹
- 中文名：基數排序法
- 過程：數據結構，基數排序的過程
- 情況：最低位優先法用於單關鍵字的情況
- 類型：排序的實例模擬、排序的算法
基數排序的基本思想,基數排序的實例模擬,基數排序的算法,
基數排序的基本思想
n個記錄的關鍵字進行排序，每個關鍵字看成是一個d元組：
ki=(ki1, ki2,..., kid)
其中
c0 <=kij <=cr-1 ( 1 <=i <=n, 1 <=j <=d )
排序時先按kid 的值，從小到大將記錄分到r（稱為基數）個盒子中，再依次收集；然後按kid-1的值再這樣作。直至按ki1分配和收集序列為止，排序結束。
在關鍵字為數字時，r=10, 0 <=ci <=9， 1 <=i <=d；
在關鍵字為字母時 r=26, ’A’ <=ci <=’Z’, 1 <=i <=d。
基數排序的實例模擬
設原有一串數值為
73, 22, 93, 43, 55, 14, 28, 65, 39, 81
首先根據個位數的數值，在走訪數值時將它們分配至編號0到9的桶子中：
0
1 81
2 22
3 73 93 43
4 14
5 55 65
6
7
8 28
9 39
接下來將這些桶子中的數值重新串接起來，成為以下的數列：
81, 22, 73, 93, 43, 14, 55, 65, 28, 39
接著再進行一次分配，這次是根據十位數來分配：
0
1 14
2 22 28
3 39
4 43
5 55
6 65
7 73
8 81
9 93
接下來將這些桶子中的數值重新串接起來，成為以下的數列：
14, 22, 28, 39, 43, 55, 65, 73, 81, 93
這時候整個數列已經排序完畢；如果排序的對象有三位數以上，則持續進行以上的動作直至最高位數為止。
基數排序的算法
首先定義新的數據類型：
chtype=c1..crd;
struct node{
chtype key[1..d];
anytype otheritem;
int next;
}R[n+1]
(1)[初始化]
for (i=0;i <n;i++) R[i].next=i+1;
R[n].next=0;
(2)[準備] p=1; /* 指向靜態鍊表中第一個元素 */
(3)[排序]
while (i=d;i> 0;i--)
{ ① [給Q初始化]
循環 j=c0,c1,…,cn-1,執行
Q[j].f=0; Q[j].e=0 /* 隊頭、隊尾指針為0 */
② [分配] 循環反覆執行下列語句，直至p=0
(a) k=R[p].key[i] /* 取關鍵字的第i個字元 */
(b) IF Q[k].f=0 THEN Q[k].f=p ELSE R[Q[k].e].next=p
(c) Q[k].e=p /* 修改隊頭隊尾指針 */
(d) p=Q[p].next; /* 取關鍵字的下一個字元 */
③ [收集]
(a) j=c0
(b) 循環 當Q[j].f=0時，反覆執行
j=succ(j)
(c) p=Q[j].f; t=Q[j].e
(d) 循環 k=succ(j),…,cr-1,執行
若Q[k].f <> 0,則R[t].next=Q[k].f; t=Q[k].e
(e) R[t].next=0 /* 靜態鍊表尾 */
[算法結束]
