数据结构，基数排序的过程，就是将最低位优先法用于单关键字的情况。基数排序的基本思想、排序的实例模拟、排序的算法等。

1、基数排序的基本思想

2、基数排序的实例模拟

3、基数排序的算法

1、基数排序的基本思想

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。

2、基数排序的实例模拟

设待排序文件各记录的关键字为288，371，260，531，287，235，56，299，18，23。这时 r=10, d=3。进行3趟分配和3趟收集。

基数排序可以采用顺序存储方式。使用R数组存放待排序记录，用r个数组存放分配时的r个队列。分配一次和收集一次都需要n次移动，d遍分配和收集，共需2dn移动。每个队列最大为n，共需rn个结点。

若采用链式存储方式，在R数组中，每个记录设一个next字段，存放下一结点的下标（静态链表）。记录的移动次数降为0，辅助空间为O(n+r)，分配时间O(n)，收集时间O(n)，时间复杂度O(d(n+r))。

3、基数排序的算法

首先定义新的数据类型：

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 /* 静态链表尾 */

[算法结束]