基数排序
基于比较的排序 只需要定义好两个对象之间怎么比较即可，对象的数据特征并不关心，很通用。
不基于比较的排序 和比较无关的排序，对于对象的数据特征有要求，并不通用。 计数排序，非常简单，但是数值范围比较大了就不行了。 基数排序的实现细节，非常优雅的一个实现。 关键点：前缀数量分区的技巧、数字提取某一位的技巧。
时间复杂度 $0(n)$，额外空间复杂度 $0(m)$，需要辅助空间做类似桶的作用，来不停的装入、弹出数字。 一般来讲，计数排序要求，样本是整数，且范围比较窄 一般来讲，基数排序要求，样本是10进制的非负整数 如果不是就需要转化，代码里做了转化，并且代码里可以设置任何进制来进行排序 一旦比较的对象不再是常规数字，那么改写代价的增加是显而易见的，所以不基于比较的排序并不通用
算法步骤
- 预处理负数（处理包含负数的场景）
- 找到数组最小值minnum
- 将所有元素减去minnum转化为非负整数
- 计算转化后的最大值maxnum
- 计算最大位数
1
bits = getBits(maxnum) // 在BASE进制下的位数
- 基数排序核心流程：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
for 每一位（从最低位到最高位）: a. 初始化词频数组cnts（大小=BASE） b. 统计当前位的词频： for 每个数字num in arr: digit = (num / offset) % BASE cnts[digit]++ c. 转换词频为前缀和数组： for i from 1 to BASE-1: cnts[i] += cnts[i-1] d. **逆序填充辅助数组**（保证排序稳定性）： for i from n-1 downto 0: digit = (arr[i]/offset) % BASE help[--cnts[digit]] = arr[i] e. 数组拷贝： arr = help offset *= BASE // 切换到更高位
- 恢复原始数值：
- 所有元素加回minnum
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
const int BASE = 10; // BASE进制下
// 计算整数x的位数
int getBits(int x) {
int res = 0;
while (x != 0) {
x /= BASE;
res++;
}
return res;
}
// 前提：arr中的元素都是BASE进制下的非负整数
void radixSort(vector<int> &arr, int bits) { // bits是arr中最大值在BASE下有几位
int n = arr.size();
vector<int> help(arr.size(), 0);
for (int offset = 1; bits > 0; offset *= BASE, bits--) {
vector<int> cnts(10, 0); // cnts用来做词频统计
for (int i = 0; i < arr.size(); i++) {
cnts[(arr[i] / offset) % 10]++; // 提取某一位的词频
}
for (int i = 1; i < BASE; i++) {
cnts[i] = cnts[i] + cnts[i - 1]; // 处理成前缀次数累加的形式
}
for (int i = n - 1; i >= 0; i--) {
// 前缀分区的技巧
help[--cnts[(arr[i] / offset) % BASE]] = arr[i]; //
}
for (int i = 0; i < n; i++) {
arr[i] = help[i];
}
}
}
// 基数排序（可包含负数）
void sortArray(vector<int> &arr) {
int n = arr.size();
int minnum = INT_MAX;
for (int i = 0; i < n; i++) {
minnum = min(minnum, arr[i]);
}
int maxnum = INT_MIN;
for (int i = 0; i < n; i++) {
arr[i] -= minnum;
maxnum = max(maxnum, arr[i]);
}
radixSort(arr, getBits(maxnum));
for (int i = 0; i < n; i++) {
arr[i] += minnum;
}
}
