RadixSort

基数排序(Radix sort)是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数,所以基数排序也不是只能使用于整数。基数排序的发明可以追溯到 1887 年 Herman Hollerith 在打孔卡片制表机(Tabulation Machine)上的贡献。

基本原理

将所有待比较正整数统一为同样的数位长度,数位较短的数前面补零。然后,从最低位开始进行基数为 10 的计数排序,一直到最高位计数排序完后,数列就变成一个有序序列(利用了计数排序的稳定性)。

算法步骤

  • 将所有待比较数值(正整数)统一为同样的数位长度,数位较短的数前面补零
  • 从最低位开始,依次进行一次排序
  • 从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列

动画演示

RadixSort

参考实现

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
import java.util.Arrays;

/**
* @author wylu
*/
public class RadixSort {

//基数
private static final int RADIX = 10;

//获取数字的位数
private static int getDigitLength(int digit) {
return (digit == 0) ? 1 : (int) Math.log10(digit) + 1;
}

//获取数组中数字的最大位数
private static int getMaxLength(int[] arr) {
int maxLength = 0;
for (int e : arr) {
int len = getDigitLength(e);
if (len > maxLength) maxLength = len;
}
return maxLength;
}

//获取数x第d位上的数字
private static int getDigit(int x, int d) {
return x / (int) (Math.pow(10, d - 1)) % 10;
}

//根据元素的第d位数字,对数组arr进行计数排序
private static void countingSort(int[] arr, int d) {
int[] counts = new int[RADIX];
for (int e : arr) {
counts[getDigit(e, d)]++;
}

for (int i = 1; i < RADIX; i++) {
counts[i] += counts[i - 1];
}

int[] tmp = new int[RADIX];
for (int i = arr.length - 1; i >= 0; i--) {
//根据当前位数字,把每个元素arr[i]放到临时数组tmp中的正确位置上
//当再遇到当前位数字x相同的元素时,会将其放在当前元素的前一个位置上保证计数排序的稳定性
tmp[--counts[getDigit(arr[i], d)]] = arr[i];
}
System.arraycopy(tmp, 0, arr, 0, tmp.length);
}

//最低位优先 LSD (Least sgnificant digital)
public static void lsdRadixSort(int[] arr) {
int maxLength = getMaxLength(arr);
//从低位到高位
for (int d = 1; d <= maxLength; d++) {
//根据第d位数字对arr进行计数排序
countingSort(arr, d);
}
}

public static void main(String[] args) {
// int[] arr = {3, 1, 4, 9, 6, 0, 7, 2, 5, 8};
int[] arr = {20, 90, 64, 289, 998, 365, 852, 123, 789, 456};
RadixSort.lsdRadixSort(arr);
System.out.println(Arrays.toString(arr));
}
}

复杂度分析

排序算法 平均时间复杂度 最好情况 最坏情况 空间复杂度 排序方式 稳定性
基数排序 \(O(nm)\) \(O(nm)\) \(O(nm)\) \(O(n+m)\) Out-place 稳定

m 为数组中数字的最大位数

References

https://en.wikipedia.org/wiki/Radix_sort

https://mp.weixin.qq.com/s?__biz=MzI1MTIzMzI2MA==&mid=2650562543&idx=1&sn=c82892b85e1de790766896c6d80d7b3c&chksm=f1fee96cc689607a11ccc109098d070d38ef0bad61c0390fe01348b631bbd492945b6f2b0601&scene=0#rd

https://youliao.163yun.com/api-server/rss/xiaomi/item/IN2WDOMKAWVNTZV.html?ref=browser_news&s=mb&cp=cn-netease-youliao-browser&docid=44797c69e120935b2c4790d933d02a9b&itemtype=news&cateCode=rec&category=%E7%A7%91%E6%8A%80