鱼喃

听！布鲁布鲁，大鱼又在那叨叨了

基数排序（Radix sort）---线性阶的排序算法

Posted on Views: 99+

基数排序是一种基于多关键词的非比较排序算法。基数排序是一种用在老式穿卡机上的算法。一张卡片有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
118
/**
 * 基数排序
 * 用链表实现
 */
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中的队列

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