基数排序
【注】参考自教材「算法导论」。
1. 简介
基数排序属于非比较排序算法类，故其时间复杂度不受比较排序算法时间复杂度下界的限制。基数排序对排序关键字的最低数位到最高数位中的每一数位采用其他排序算法进行排序。基数排序时间复杂度可以达到 O(d(n+k))（这中情况下对每一数位采用的排序算法为计数排序）。其中，k 为待排序序列的排序关键字每一数位的最大范围，ddd 是排序关键字的数位数目。 计数排序要求每一数位排序所使用的排序算法都是稳定的，否则将影响计数排序的正确性。基数排序是稳定的，其原址性取决于对每一数位所使用的排序算法的原址性。
2. 思想
类比于多关键字元素序列的排序思想，先比较第一关键字，再比较第二关键字、…… ，这样的排序思想属于自顶向下的思想，即先根据第一关键字排序后将序列分割为小的子序列，然后再根据第二关键字排序……，以此类推。这样做有一个不利之处在于对每个关键字排序需要限定区间，根据第一关键字排序的区间为整个区间，根据第二关键字排序的区间限定为第一关键字相同的区间，以此类推。 然而本质上不同子序列区间对第 i 个关键字排序的操作都是一样的，只是由于第 i−1 个关键字规定了其范围为第 iii 个关键字相同的区间。而第 i−1 个关键字排序同理。即本质是由于自顶向下导致的区间的划分，而不同区间排序步骤没有任何区别。 于是，我们可以逆向思考。如果采用自底向上的方式，就不用考虑区间的划分问题了。即先从优先级最低的关键字对整个序列排一次序，再从优先级次最低的关键字对整个序列排一次序，…… 。
【注】采用自底向上的对多关键字排序的思想需要注意，每一轮采用的排序算法必须是稳定的，否则排序结果的正确性无法保证。因为对于第 i 个关键字排序时，如果两个元素的第 i 关键字相同，不能改变它们的位置，因为此时它们的位置是由第 i+1 个关键字确定的（即上一轮排序），所以每一轮的排序算法都必须是稳定的。
而基数排序则是将排序关键字的每一数位对应每一个关键字，高数位对应高优先级关键字，低数位对应低优先级关键字，然后采用自底向上的思想对每一数位进行排序。基数排序一般采用计数排序对每一数位进行一轮排序，这样时间复杂度就是线性的，为 O(d(n+k))；由于计数排序是非原址的，所以如此实现的基数排序也是非原址的，且空间复杂度取决于一轮计数排序所需的空间复杂度（故适用性比计数排序广）。
3. 实现
3.1 伪代码
RadixSort(A, d, k) {
for i = 1 to d
// 每一数位的值范围属于区间 [0,k)
使用稳定的排序算法对基于数位 i 为关键字的数组 A 进行排序
}3.2 模板
以下模板代码采用计数排序对每一数位进行一轮排序。
#include <bits/stdc++.h>
using namespace std;
#ifndef _RADIX_
#define _RADIX_
#define ll int
#define MAXN 100005
// 基数排序
template < typename T >
struct Radix {
ll C[MAXN];
ll K[MAXN];
ll SK[MAXN];
T SA[MAXN];
Radix() {}
// 基数排序
//（关键字数组不会改变，待排序数组变为有序）
void radixSort(T *bA, T *eA, ll *bK, ll *eK, ll d, ll n = 10) {
ll len_A = eA - bA;
ll len_K = eK - bK;
T *A = bA;
// 判断关键字数组大小与元素数组大小是否吻合
assert(len_A == len_K);
// 拷贝关键字数组（因后续需修改）
memcpy(K, bK, sizeof(ll)*len_K);
// 对每一数位进行计数排序
for(int i = 0; i < d; ++i) {
// 初始化计数数组
for(ll j = 0; j < n; ++j) {
C[j] = 0;
}
// 统计关键字次数
for(ll j = 0; j < len_K; ++j) {
C[K[j]%n]++;
}
// 计算 <= j 的关键字次数
for(ll j = 1; j < n; ++j) {
C[j] = C[j] + C[j-1];
}
// 初始化排序数组
for(ll j = len_A-1; ~j; --j) {
SA[C[K[j]%n]-1] = A[j];
SK[C[K[j]%n]-1] = K[j]/n;
C[K[j]%n]--;
}
// 将排好序的数组赋值给原数组
memcpy(A, SA, sizeof(T)*len_A);
memcpy(K, SK, sizeof(T)*len_K);
}
}
};
#endif