排序算法(八):Radix Sort 基数排序

Radix Sort 基数排序是对计数排序的改进,该算法可以支持针对浮点、字符串等类型元素进行排序。其主要思想是将排序元素按数位分割依次排序,从而实现整体有序。其同样可以具有线性时间的性能

abstract.jpeg

基本原理

在对非负整数进行基数排序时,需要首先将排序元素统一为相同的数位长度,数位不足的排序元素可以添加前导零的方式实现数位长度统一对齐;然后从排序元素的最低位(个位)开始进行排序,直到完成对最高位的排序,此时即实现了对排序元素的整体排序。而对每个数位进行排序的过程则是通过(稳定的)计数排序完成的,故基数排序同样是稳定的。由于我们是从排序元素的最低位向最高位依次排序的,故这种方式被称为最低位(LSD,Least Significant Digit)法;反之,如果是从排序元素的最高位向最低位依次排序的,则被称之为最高位(MSD,Most Significant Digit)法

实际上,基数排序算法对排序元素的类型不要求一定是非负整数才可以进行,其对于字符串、浮点数等类型均可适用。其关键在于要求排序元素的数位长度统一。例如对整数排序时,如果排序元素中含有负数,则可以对排序元素均加上一个数使其全部为非负整数;如果元素类型是字符串的话,在计数排序过程中,可以直接使用该位字符对应ASCII码值进行计数,对于长度不足的字符串,可直接在其后面补0实现长度对齐。即在计数排序过程中,如果发现某位字符是为对齐所填充的0的话,则可认为其对应的ASCII码值为0进行计数,因为字符’A’所对应的ASCII码值是65,字符’0’所对应的ASCII码值是48,均比0大。这样即可保证基数排序的结果是符合字典序的

实现

这里是一个通过Java实现的对非负整数类型的元素进行基数排序的实例,来帮助大家更好地理解该算法

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
/**
* 基数排序
*/
public class RadixSort {
/**
* 升序排列
*/
public static void sort() {
int[] array = getTestCase(); // 获取测试用例
System.out.println("before sort: " + Arrays.toString(array) );
array = radixSortByLSD(array);
System.out.println("after sort: " + Arrays.toString(array) );
}

/**
* 基数排序: LSD(最低位)法
*/
private static int[] radixSortByLSD(int[] array) {
int radix = 10; // 基数(数位的取值范围为[0,9])
int size = array.length;
int[] sortedArray = new int[size]; // 排序结果数组

// 计算待排序元素的最大位数 d
int maxDigits = -1;
for(int element : array ) {
maxDigits = Math.max( getDigits(element), maxDigits);
}

// 从最低位开始遍历排序(计数排序)直到最高位为止
for(int i=1; i<=maxDigits; i++) {
// 对元素指定位i上的数进行计数排序
int[] counts = new int[radix]; // 创建次数统计数组
// 统计次数
for(int element : array) {
// 获取排序元素第i位上的数
int num = getNumberByIndex(element, i);
counts[num]++;
}
// 计算统计数组的累加值
for(int j=1; j<radix; j++) {
counts[j] = counts[j-1] + counts[j];
}
// 倒序遍历排序数组,保证稳定性
for(int j=size-1; j>=0; j--) {
// 获取排序元素第i位上的数
int num = getNumberByIndex(array[j], i);
// 该排序元素在对第i位进行计数排序后的排序位置, 因为数组索引从0开始计算,故应对排序位置减1
int sortIndex = counts[num]-1;
// 将原数组元素放入排序后的位置上
sortedArray[sortIndex] = array[j];
// 下一个重复的元素,应排前一个位置,以保证稳定性
counts[num]--;
}
array = sortedArray.clone(); // 本次排序结果用于下一次计数排序
}
return array;
}

/**
* 计算整数位数
* @param num
* @return
*/
private static int getDigits(int num) {
if(num==0) {
return 1;
}
int digits = (int)Math.log10(num) + 1;
return digits;
}

/**
* 取出num中某一数位上的数
* @param num
* @param index 1: 个位; 2: 十位; 3: 百位...
* @return
*/
private static int getNumberByIndex(int num, int index) {
int digits = getDigits(num);
if(index>digits) {
return 0; // num不足指定位数,则使用前导零填充
}
int numInIndex = num / (int)Math.pow(10, index-1) % 10;
return numInIndex;
}

/**
* 获取测试用例
*/
private static int[] getTestCase() {
int[] caseArray = {220, 134, 0, 153, 2, 87};
return caseArray;
}
}

测试结果如下:

figure 1.png

特性

N为排序元素的数目,r为基数,d为排序元素的最大位数(长度)。当d为常数且r=O(N)时,其具有线性时间复杂度

table 1.png

参考文献

  1. 算法导论 · 第3版
  2. 计算机程序设计艺术(第3卷):排序与查找 高德纳(Donald E.Knuth) 著
0%