排序算法系列——基数排序

基数排序不同于其他的七种排序算法,它是基于一种分配法,而非比较。基数排序属于“分配式排序”(distribution sort),基数排序法又称“桶子法”(bucket sort)或bin sort,顾名思义,它是透过键值的部份资讯,将要排序的元素分配至某些“桶”中,藉以达到排序的作用。它的灵感来自于队列(Queue),它最独特的地方在于利用了数字的有穷性(阿拉伯数字只有0到9的10个)。

基本思想

我们考虑对整数进行基数排序的过程,对于整数,我们可以将其分成个位、十位、百位、。。。基数排序就是先对元素的个位进行排序,然后再对十位进行排序,。。。最终按最高位进行排序完成整个排序。逻辑可以理解为,比如正常情况下我们排序两个整数,我们首先对比的是十位然后是个位,现在我们颠倒过来先排序个位,再排序十位,如果十位相同上一步我们已经按个位排好序,所以还是有序的。其实基数排序也有另一种方式MSD,即从高位开始。

实现要点

首先我们需要一个能够放下所有一位数的桶(bucket),还好阿拉伯数字只有10个,所以我们只需要10个bucket就可以搞定,但是在将所有元素放入bucket时肯定会出现多个元素放入一个bucket的情况,这时候就需要使用链表来解决了(也有使用二维数组的方式,但是空间需要n^2,当排序元素很多时肯定有点吃不消),同时为了方便往bucket中遍历元素以及添加元素,我们让bucket包含两个指针,一个指向bucket中第一个元素(head),另一个指向最后一个元素(tail),而bucket中每个元素都是一个Node,Node中包含一个排序序列中的值(val)以及一个指向下一个元素的指针(next)。
有了桶,下一步就是需要将所有数值从个位开始依次放入桶,然后再按顺序取出放回原数组了,这里有个地方需要注意下,就是如何循环到数组中所有元素的最高位就终止循环,这里有两个解决方法:
(1)首先遍历一遍数组,找到最大值,确定最高位
(2)一直循环直到所有元素的指定位数都是0为止
第一种方法需要O(n)次的比较,而第二次需要计算每个值在指定位数的值,同时还需要将其放入桶中。我的实现需要第一种方式。
到这里基本就可以实现出一个基数排序了,下面就看看如何实现。
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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
package com.vicky.sort;

import java.util.Random;

/**
* 基数排序
*
* @author Vicky
*
*/

public class RadixSort {
private static final int RADIX = 10;

public static void sort(Integer[] data) {
long start = System.nanoTime();
if (null == data) {
throw new NullPointerException("data");
}
if (data.length == 1) {
return;
}
// 遍历一遍,找到最大值,确定最高位数
int max = Integer.MIN_VALUE;
int i = 0;
for (; i < data.length; i++) {
if (data[i] > max) {
max = data[i];
}
}
// 计算最高位数
int maxDigit = String.valueOf(max).length();
Bucket[] temp = new Bucket[RADIX];// 用于保存各个位数的bucket
for (int num = 0; num < maxDigit; num++) {
// 将每个元素指定位数的值放入对应的bucket中
for (i = 0; i < data.length; i++) {
int val = data[i] / pow(RADIX, num);
Node node = new Node(data[i], null);
Bucket tmp = temp[val % RADIX];
if (null == tmp) {
temp[val % RADIX] = new Bucket(node, node);
} else {
tmp.getTail().setNext(node);
tmp.setTail(node);
}
}
// 将temp中保存的元素按顺序更新到原数组中
int index = 0;
for (i = 0; i < temp.length; i++) {
if (null == temp[i]) {
continue;
}
Node node = temp[i].getHead();
data[index++] = node.getValue();
while (null != node.getNext()) {
data[index++] = node.getNext().getValue();
node = node.getNext();
}
// 顺便重置temp
temp[i] = null;
}
}

System.out.println("use time:" + (System.nanoTime() - start) / 1000000);
}

/**
* 计算指定基数的指定幂的值
*
* @param digit
* 基数,如10
* @param num
* 幂次值,从0开始,10^0=1
* @return
*/

private static int pow(int digit, int num) {
int val = 1;
for (int i = 0; i < num; i++) {
val *= digit;
}
return val;
}

/**
* <p>
* 桶,用于存放数组
* </p>
*
* @author Vicky
* @date 2015-8-21
*/

private static class Bucket {
private Node head;
private Node tail;

public Bucket(Node head, Node tail) {
super();
this.head = head;
this.tail = tail;
}

public Node getHead() {
return head;
}

public Node getTail() {
return tail;
}

public void setTail(Node tail) {
this.tail = tail;
}
}

/**
* <p>
* 节点,用于解决桶中存放多个元素问题
* </p>
*
* @author Vicky
* @date 2015-8-21
*/

private static class Node {
private int value;
private Node next;

public Node(int value, Node next) {
super();
this.value = value;
this.next = next;
}

public int getValue() {
return value;
}

public Node getNext() {
return next;
}

public void setNext(Node next) {
this.next = next;
}
}

public static void main(String[] args) {
Random ran = new Random();
Integer[] data = new Integer[10000000];
Integer[] data2 = new Integer[data.length];
Integer[] data3 = new Integer[data.length];
for (int i = 0; i < data.length; i++) {
data[i] = ran.nextInt(100000);
data2[i] = data[i];
data3[i] = data[i];
}
MergeSort.sort(data);
QuickSort.sort(data2);
RadixSort.sort(data3);
// SortUtils.printArray(data);
// SortUtils.printArray(data2);
// SortUtils.printArray(data3);
}
}

效率分析

(1)时间复杂度
O(kn)

基数排序的时间复杂度是 O(k·n),其中n是排序元素个数,k是数字位数。注意这不是说这个时间复杂度一定优于O(n·log(n)),因为k的大小一般会受到 n 的影响。 以排序n个不同整数来举例,假定这些整数以B为底,这样每位数都有B个不同的数字,k就一定不小于logB(n)。由于有B个不同的数字,所以就需要B个不同的桶,在每一轮比较的时候都需要平均n·log2(B) 次比较来把整数放到合适的桶中去,所以就有:
k 大于或等于 logB(n)
每一轮(平均)需要 n·log2(B) 次比较
所以,基数排序的平均时间T就是:
T ≥logB(n)·n·log2(B) = log2(n)·logB(2)·n·log2(B)= log2(n)·n·logB(2)·log2(B) = n·log2(n)
所以和比较排序相似,基数排序需要的比较次数:T ≥ n·log2(n)。故其时间复杂度为Ω(n·log2(n)) = Ω(n·log n) 。

(2)空间复杂度
O(radix+n)
radix个bucket,以及n个Node。
(3)稳定性
稳定
假设一组元素:12(a),23,12(b),34,15,首先我们按个位分桶得到bucket(1)里面是12(a),12(b),取出后还是12(a),12(b)所以顺序并没有变化。

基数排序虽然看着感觉效率很高,其实经过测试效率并不如快速排序和归并排序,但是比其他的O(n^2)的排序算法效率肯定是高的。因为基数排序需要操作链接,对于链表的操作肯定不如数组效率高。不过基数排序可以适用于非数值排序,比如字符串。对于一组字符串进行排序,其他的排序算法就无法适用了,但是可以运用基数排序,按字符串个每位字符进行划分入桶,再进行排序即可,不过得先确定有多少个不同字符,要是包含全部字符,那就没法玩了。下面引用一篇文章介绍的基数排序的适用范围吧。

基数排序从低位到高位进行,使得最后一次计数排序完成后,数组有序。其原理在于对于待排序的数据,整体权重未知的情况下,先按权重小的因子排序,然后按权重大的因子排序。例如比较时间,先按日排序,再按月排序,最后按年排序,仅需排序三次。但是如果先排序高位就没这么简单了。基数排序源于老式穿孔机,排序器每次只能看到一个列,很多教科书上的基数排序都是对数值排序,数值的大小是已知的,与老式穿孔机不同。将数值按位拆分再排序,是无聊并自找麻烦的事。算法的目的是找到最佳解决问题的方案,而不是把简单的事搞的更复杂。基数排序更适合用于对时间、字符串等这些整体权值未知的数据进行排序。这时候基数排序的思想才能体现出来,例如字符串,如果从高位(第一位)往后排就很麻烦。而反过来,先对影响力较小,排序排重因子较小的低位(最后一位)进行排序就非常简单了。这时候基数排序的思想就能体现出来。又或者所有的数值都是以字符串形式存储,就象穿孔机一样,每次只能对一列进行排序。这时候基数排序也适用,例如:对{“193”;”229”;”233”;”215”}进行排序。

参考文章

java基数排序
Java排序算法总结(八):基数排序