排序：基数排序算法分析

1.算法思想

假设长度为n的线性表中每个结点aj的关键字由d元组$(k_j^{d-1},k_j^{d-2},k_j^{d-3},...,k_j^1,k_j^0)$组成，
其中，$0<=k_j^i<=r-1(0<=j<n,0<=i<=d-1)$，r称为“基数”。

基数排序得到递减序列的过程如下:

1. 初始化︰设置r个空队列，$Q_{r-1}，Q_{r-2,}...，Q_0$
2. 按照各个关键字位权重递增的次序(个、十、百)，对d个关键字位分别做“分配”和“收集”
3. 分配:顺序扫描各个元素，若当前处理的关键字位，则将元素插入Qx队尾，一趟分配耗时O(n)
4. 收集:把$Q_{r-1},Q_{r-2},...，Q_0$各个队列中的结点依次出队并链接，一趟收集耗时O(r）

例如：收集:得到一个按“百位”递减排列的序列，若“百位”相同则按“十位"递减排列，若“十位”还相同则按“个位”递减排列。

基数排序不是基于“比较”的排序算法。

2.算法效率分析

基数排序通常基于链式存储实现：

typedef struct LinkNode {
    ElemType data;
    struct LinkNode *next;
} LinkNode, *LinkList;
1
2
3
4

链式队列设计：

typedef struct {//链式队列
    LinkNode *front, *rear;//队列的队头和队尾指针
} LinkQueue;
1
2
3

1.空间复杂度

需要r个辅助队列，空间复杂度= O(r）。

2.时间复杂度

一趟分配O(n)，一趟收集O（r)，总共d趟分配、收集，总的时间复杂度=O(d(n+r))

3.稳定性

基数排序是稳定的。

3.基数排序的应用

1.学生年龄排序

某学校有10000学生，将学生信息按年龄递减排序
生日可拆分为三组关键字:年(1991-2005)、月(1-12)、日(1-31)

权重:年>月>日，年、月、日越大，年龄越小。

1. 第一趟分配、收集（按“日"递增)
2. 第二趟分配、收集(按“月”递增)
3. 第三趟分配、收集（按“年”递增)

若采用基数排序，时间复杂度= O(d(n+r))，约等于 O(30000)
若采用$O(n^2)$的排序，约等于$O(10^8)$
若采用$O(nlo{g}_{2}n)$的排序，约等于O(140000)

可以看到这里采用基数排序时间复杂度会更低。

2.基数排序适合解决的问题

• ①数据元素的关键字可以方便地拆分为d组，且d较小（反例:给5个人的身份证号排序）
• ②每组关键字的取值范围不大，即r较小（反例:给中文人名排序）
• ③数据元素个数n较大（擅长:给十亿人的身份证号排序）