基数排序的简单实现

基数排序

基数排序是一种基于分配的排序(空间换时间),不同于常见的基于比较的排序(冒泡、快排、归并…等)。

基于比较的排序时间复杂度通常是O(n^2)或者O(nlogn),下限是O(nlogn);

基于分配的排序算法的时间复杂度可以达到O(n),但需要消耗额外空间;

在某些时候,基数排序的效率高于其它基于比较的排序算法(快排、归并等)。

原理

原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。进行了c次(c是整数的位数)比较之后,得到一个有序的数组。
基数排序是桶排序的扩展,每一次排序建立在桶排序的基础上。

步骤

1. 将每个数字统一位数长度(数位短的前面补0);
2. 从最低位(个位)开始,依次进行每次排序;
3. 最高位排序完成后,数组就变成了有序数组。

实例分析

通过基数排序对一个无序数组进行排序{53, 542, 3, 63, 14, 214, 154, 748, 616},它的示意图如下:

image

比较过程

结合上图分析比较过程。
每次比较,根据相应位数上的值,将元素放入对应的桶(0-10)中。

经过第三次排序,如图一,得到一个有序的数组。

实现

计算排序的次数

排序的次数即数组统一的位数(也是最大元素的位数),在这里是 3 位,总共需要比较3次。

1
2
3
4
5
6
7
8
9
10
11
12
13
//获取最大值
int max = a[0];
for (int i = 0; i < a.length; i++) {
if (max < a[i]) {
max = a[i];
}
}
//根据最大值确定排序的遍数(如369三位数,就是3遍)
int time = 0;
while (max > 0) {
max = max / 10;
time ++;
}
排序过程

每一次排序之后,都要根据排序的结果记录新的顺序,以便下一次排序。
思路如下:
1. 将桶数组看成是一个只有10个元素(0-9)的队列,建立该队列(父队列);
2. 父队列中的每一个元素都代表一个子队列,用于存放每个桶中的元素,可能0个也可能多个;

注:采用数组ArrayList来代替子队列,也可以采用链表

1
2
3
4
5
6
//建立一个主队列,包含10个子队列
List<ArrayList> queue = new ArrayList<ArrayList>();
for (int i = 0; i < 10; i++) {
ArrayList<Integer> subQueue = new ArrayList<>();
queue.add(subQueue);
}

3. 分配数组元素

将每一个数组元素分配进入相应的桶中,即子队列中。
每次分配时,i 的值表示获取元素对应位数上的数字:
i = 0 ,表示个位;
i= 1,表示十位;
i = 2, 表示百位;

1
2
3
4
5
6
7
8
9
//分配数组元素
for (int j = 0; j < a.length; j++) {
int c = a[j] % (int)Math.pow(10, i + 1); //当前位上的数字
int x = c / (int)Math.pow(10, i); //子队列的序号
//System.out.println(x);
ArrayList<Integer> subQueue = queue.get(x); //从父队列获取子队列
subQueue.add(a[j]);
queue.set(x, subQueue);
}

代码实现
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
public static void radisSort(int[] a) {
//获取最大值
int max = a[0];
for (int i = 0; i < a.length; i++) {
if (max < a[i]) {
max = a[i];
}
}
//根据最大值确定排序的遍数(如369三位数,3遍)
int time = 0;
while (max > 0) {
max = max / 10;
time ++;
}
//建立一个主队列,包含10个子队列
List<ArrayList> queue = new ArrayList<ArrayList>();
for (int i = 0; i < 10; i++) {
ArrayList<Integer> subQueue = new ArrayList<>();
queue.add(subQueue);
}
//time次排序
for (int i = 0; i < time; i++) {
//分配数组元素
for (int j = 0; j < a.length; j++) {
int c = a[j] % (int)Math.pow(10, i + 1); //当前位上的数字
int x = c / (int)Math.pow(10, i); //子队列的序号
//System.out.println(x);
ArrayList<Integer> subQueue = queue.get(x); //从父队列获取子队列
subQueue.add(a[j]);
queue.set(x, subQueue);
}
//分配结束后,记录新的顺序
int k = 0;
for (int n = 0; n < 10; n++) {
//取出有元素的子队列
while (queue.get(n).size() > 0) {
ArrayList<Integer> subQueue = queue.get(n);
a[k ++] = subQueue.get(0); //头部元素
subQueue.remove(0); //移除元素
}
}
//打印每次排序后的新数组
// for (int m : a) {
// System.out.print(m + " ");
// }
}
//打印最终排好序的数组
for (int m : a) {
System.out.print(m + " ");
}
}
public static void main(String[] args) {
int[] a = {53, 542, 3, 63, 14, 214, 154, 748, 616};
radisSort(a);
}

输出:

1
3 14 53 63 154 214 542 616 748

以上,就是基数排序的大致过程。