逍遥游

基数排序(Radix sort)---线性阶的排序算法

基数排序是一种基于多关键词的非比较排序算法。基数排序是一种用在老式穿卡机上的算法。一张卡片有80列,每列可在12个位置中的任一处穿孔。排序器可被机械地”程序化”以检查每一迭卡片中的某一列, 再根据穿孔的位置将它们分放12个盒子里。这样,操作员就可逐个地把它们收集起来。其中第一个位置穿孔的放在最上面,第二个位置穿孔的其次,等等。

算法原理(以正整数为例)

基数排序有LSD(Least Significant Dight)MSD(Most Significant Dight)两种。MSD是从最主要关键词开始排序,而LSD是从最次关键词开始排序。由于MSD需要额外的空间,一般用到的是LSD方法,本文讲的都是LSD方法。

排序的要求是对任意两个数,a大于b,当且仅当从两数的第某位开始a大于b,也就是说前面的位权重大于后面的,我们先保证最后一位是有序的,这就保证了仅当最后一位不同的数是有序的,然后根据次末位进行排序,保证了后两位不同的数是有序的(注意:这里说的排序并不是一般意义上的排序方法)。

算法过程

首先,我们要有十个桶,和一个大桶(桶里的数根据先到先出的顺序,是一个队列,下文不作说明了)

第一步,把数组里的数依次放到桶里;

第二步,把倒数第i位(i从1开始)为k的数放到第k个桶里;

第三步,从第一个桶开始,把所有数放到大桶里;

第四步,重复第二、三步,直到所有数中的最大数倒数第i位是0;

排序完成

算法演示

例如对{41,467,334,500,169,724,478,358,962,464}进行基数排序。

1、{500},{41},{962},{334,464},{467},{478,358},{169}

2、{500,41,962,334,464,467,478,358,169}

3、{500},{724},{334},{41},{358},{962,467,169},{478}

4、{500,724,334,41,358,962,467,169,478}

5、{041},{169},{334,358},{464,467,478},{500},{724},{962}

6、{041,169,334,358,464,467,478,500,724,962}

时间复杂度

基数排序的时间复杂度与最大数的位数K、数的总个数N有关,一般来说是O(KN),这是正整数的情况。推广到一般情况,如果一位有B种可能性,最大的是M,那么时间复杂度是O(logB(M)*N)。值得一提的是,基数排序过程中会涉及到指针操作等等,速度稍微有点慢。如果考虑和比较排序进行对照,基数排序的形式复杂度虽然不一定更小,但由于不进行比较,因此其基本操作的代价较小,而且在适当选择的B之下,K一般不大于log_N_,所以基数排序一般要快过基于比较的排序,比如快速排序。

速度实测

写完基数排序代码之后,我很有兴致的测了一下各种排序算法处理10万规模的正整数的时间,结果发现对于同一个数据,基数排序用了0.2s,快速排序0.1s,归并排序0.4s,而插入排序竟然用了16s!(估计是代码写的太烂)(除了快速排序是STL里的,其他都是自己写的。)

排序算法(N=100000) 时间(s)
基数排序(Redix-sort) 0.1
快速排序(Quick-sort) 0.2
插入排序(Insert-sort) 0.4
归并排序(Merge-sort) 16?

算法稳定性

显然,根据LILO(先进先出)的规则,基数排序是稳定的排序。

示例代码(C++)

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
/**
* 基数排序
* 用链表实现
*/
int radix_sort(int *src, int size){
node* headers[10];
node* rears[10];
node* bigHeader=NULL;
node* bigRear=NULL;
/**
* 把数组化为链表,方便后续处理
*/
for(int i=0; i<size; i++)
{
node *tmp = new node;
tmp->value = src[i];
tmp->next = NULL;
if(bigRear == NULL)
{
bigHeader = tmp;
bigRear = tmp;
}else{
bigRear->next = tmp;
bigRear = tmp;
}
}
/**
* 最外层循环的次数与最大的数位数相同
*/
for(int s=1; ; s*=10)
{
int max=0;
/**
* 解决某些指针问题,可以无视
*/
for(int i=0; i<10; i++){
headers[i] = NULL;
rears[i] = NULL;
}
/** 按照第n+1位(s=10^n)进行分类
*
*/
for(int i=0; i<size; i++)
{
if(bigHeader->value/s > max)
{
max = bigHeader->value/s;
}
int n=(bigHeader->value/s) % 10;
if(headers[n] == NULL)
{
headers[n] = rears[n] = bigHeader;
}else
{
rears[n]->next = bigHeader;
rears[n] = bigHeader;
}
bigHeader = bigHeader->next;
rears[n]->next = NULL;
}
//麻烦的指针^-^
bigRear = NULL;
/** 从第一个分链表开始依次加到大链表中
*
*/
for(int i=0; i<10; i++)
{
while(headers[i] != NULL)
{
if(bigHeader == NULL)
{
bigHeader = bigRear = headers[i];
}else
{
bigRear->next = headers[i];
bigRear = headers[i];
}
headers[i] = headers[i]->next;
bigRear->next = NULL;
}
}
//已经处理到了最大长度的那个数
if(max <= 10)
break;
/** 输出每次循环后的结果
*
*/
for(node *tmp = bigHeader; tmp != NULL; tmp = tmp->next)
{
printf("%d ", tmp->value);
}
printf("\n");
system("pause");
}
/**
* 将链表中的数写回数组
* 不要忘了释放new的链表
*/
int i=0;
for(node *tmp = bigHeader; tmp != NULL; )
{
src[i++] = tmp->value;
tmp = tmp->next;
delete bigHeader;
bigHeader = tmp;
}
return 0;
}

代码说明

  • 代码仅能处理正整数
  • 如果待排序的数中含有负数,建议分开处理(原因见负数取模、负数除法的问题
  • 进行其他(比如a-z的字符串),需要增大桶的数量。
  • 使用了链表和大量指针是为了减少空间复杂度和方便说明,平时写的时候可以利用STL中的队列

详细代码请点击这里查看。


多说停止服务,disqus引导注册太过分,暂时不上评论系统了。有机会自己造轮子吧。邮箱:input@newnius.com