排序：基数排序算法分析
1.算法思想
假设长度为n的线性表中每个结点aj的关键字由d元组 ( k j d − 1 , k j d − 2 , k j d − 3 , . . . , k j 1 , k j 0 ) (k_{j}^{d-1},k_{j}^{d-2},k_{j}^{d-3},... ,k_{j}^{1} ,k_{j}^{0}) (kjd−1,kjd−2,kjd−3,...,kj1,kj0)组成，
其中， 0 < = k j i < = r − 1 ( 0 < = j < n , 0 < = i < = d − 1 ) 0<=k_{j}^{i}<=r-1(0<=j<n,0<=i<=d-1) 0<=kji<=r−1(0<=j<n,0<=i<=d−1)，r称为“基数”。
基数排序得到递减序列的过程如下:
- 初始化︰设置r个空队列， Q r − 1 ， Q r − 2 , . . . ， Q 0 Q_{r-1}，Q_{r-2,}...，Q_0 Qr−1，Qr−2,...，Q0
- 按照各个关键字位权重递增的次序(个、十、百)，对d个关键字位分别做“分配”和“收集”
- 分配:顺序扫描各个元素，若当前处理的关键字位，则将元素插入Qx队尾，一趟分配耗时O(n)
- 收集:把 Q r − 1 , Q r − 2 , . . . ， Q 0 Q_{r-1},Q_{r-2},...，Q_0 Qr−1,Qr−2,...，Q0各个队列中的结点依次出队并链接，一趟收集耗时O(r）
例如：收集:得到一个按“百位”递减排列的序列，若“百位”相同则按“十位"递减排列，若“十位”还相同则按“个位”递减排列。
基数排序不是基于“比较”的排序算法。
2.算法效率分析
基数排序通常基于链式存储实现：
typedef struct LinkNode {ElemType data;struct LinkNode *next;
} LinkNode, *LinkList;
链式队列设计：
typedef struct {//链式队列LinkNode *front, *rear;//队列的队头和队尾指针
} LinkQueue;
1.空间复杂度
需要r个辅助队列，空间复杂度= O(r）。
2.时间复杂度
一趟分配O(n)，一趟收集O（r)，总共d趟分配、收集，总的时间复杂度=O(d(n+r))
3.稳定性
基数排序是稳定的。
3.基数排序的应用
1.学生年龄排序
某学校有10000学生，将学生信息按年龄递减排序
生日可拆分为三组关键字:年(1991-2005)、月(1-12)、日(1-31)
权重:年>月>日，年、月、日越大，年龄越小。
- 第一趟分配、收集（按“日"递增)
- 第二趟分配、收集(按“月”递增)
- 第三趟分配、收集（按“年”递增)
若采用基数排序，时间复杂度= O(d(n+r))，约等于 O(30000)
若采用 O ( n 2 ) O(n^2) O(n2)的排序，约等于 O ( 1 0 8 ) O(10^8) O(108)
若采用 O ( n l o g 2 n ) O(nlog_2n) O(nlog2n)的排序，约等于O(140000)
可以看到这里采用基数排序时间复杂度会更低。
2.基数排序适合解决的问题
- ①数据元素的关键字可以方便地拆分为d组，且d较小（反例:给5个人的身份证号排序）
- ②每组关键字的取值范围不大，即r较小（反例:给中文人名排序）
- ③数据元素个数n较大（擅长:给十亿人的身份证号排序）