基数排序

基数排序

参考:
https://baike.baidu.com/item/%E5%9F%BA%E6%95%B0%E6%8E%92%E5%BA%8F

http://cuijiahua.com/blog/2018/01/algorithm_8.html

一、原理

基数排序(radix sort)属于“分配式排序”(distribution sort),又称“桶子法”(bucket sort)或bin sort,顾名思义,它是透过键值的部份资讯,将要排序的元素分配至某些“桶”中,藉以达到排序的作用,基数排序法是属于稳定性的排序,其时间复杂度为O (nlog(r)m),其中r为所采取的基数,而m为堆数,在某些时候,基数排序法的效率高于其它的稳定性排序法。

基本思想:将所有待比较数值(正整数)统一为同样的数位长度,数位较短的数前面补零。然后,从最低位开始,依次进行一次排序。这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。

二、步骤

  • 1、将所有数据从低位开始,按照0~9进行归类
  • 2、将归完的数据整理好,这就进行了一次排序
  • 3、重复执行前两步直到最高位也排完序了,此时整理完数据就是排完的序列

三、例子(借用百度百科的例子)

  • 第一步

以LSD为例,假设原来有一串数值如下所示:

73, 22, 93, 43, 55, 14, 28, 65, 39, 81

首先根据个位数的数值,在走访数值时将它们分配至编号0到9的桶子中:

1
2
3
4
5
6
7
8
9
10
0
1 81
2 22
3 73 93 43
4 14
5 55 65
6
7
8 28
9 39

  • 第二步

接下来将这些桶子中的数值重新串接起来,成为以下的数列:

81, 22, 73, 93, 43, 14, 55, 65, 28, 39

接着再进行一次分配,这次是根据十位数来分配:

1
2
3
4
5
6
7
8
9
10
0
1 14
2 22 28
3 39
4 43
5 55
6 65
7 73
8 81
9 93

  • 第三步

接下来将这些桶子中的数值重新串接起来,成为以下的数列:

14, 22, 28, 39, 43, 55, 65, 73, 81, 93

这时候整个数列已经排序完毕;如果排序的对象有三位数以上,则持续进行以上的动作直至最高位数为止。

LSD的基数排序适用于位数小的数列,如果位数多的话,使用MSD的效率会比较好。MSD的方式与LSD相反,是由高位数为基底开始进行分配,但在分配之后并不马上合并回一个数组中,而是在每个“桶子”中建立“子桶”,将每个桶子中的数值按照下一数位的值分配到“子桶”中。在进行完最低位数的分配后再合并回单一的数组中。

四、算法实现

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
119
#include "stdio.h"
#include "math.h"

void bucketSort3(int *p, int n);
int getLoopTimes(int num);
int findMaxNum(int *p, int n);
void sort2(int *p, int n, int loop);


//基数排序
void bucketSort3(int *p, int n)
{
//获取数组中的最大数
int maxNum = findMaxNum(p, n);
//获取最大数的位数,次数也是再分配的次数。
int loopTimes = getLoopTimes(maxNum);
int i;
//对每一位进行桶分配
for (i = 1; i <= loopTimes; i++)
{
sort2(p, n, i);
printf("第%d次循环:\t", i);
for (int j = 0; j < n; j++)
{
printf("%d\t", p[j]);
}
printf("\n");
}
}
//获取数字的位数
int getLoopTimes(int num)
{
int count = 1;
int temp = num / 10;
while (temp != 0)
{
count++;
temp = temp / 10;
}
return count;
}
//查询数组中的最大数
int findMaxNum(int *p, int n)
{
int i;
int max = 0;
for (i = 0; i < n; i++)
{
if (*(p + i) > max)
{
max = *(p + i);
}
}
return max;
}
//将数字分配到各自的桶中,然后按照桶的顺序输出排序结果
void sort2(int *p, int n, int loop)
{
//建立一组桶此处的20是预设的根据实际数情况修改
int buckets[10][20] = {};
//求桶的index的除数
//如798个位桶index=(798/1)%10=8
//十位桶index=(798/10)%10=9
//百位桶index=(798/100)%10=7
//tempNum为上式中的1、10、100
int tempNum = (int)pow((float)10, loop - 1);
int i, j;
for (i = 0; i < n; i++)
{
int row_index = (*(p + i) / tempNum) % 10;
for (j = 0; j < 20; j++)
{
if (buckets[row_index][j] == NULL)
{
buckets[row_index][j] = *(p + i);
break;
}
}
}
//将桶中的数,倒回到原有数组中
int k = 0;
for (i = 0; i < 10; i++)
{
for (j = 0; j < 20; j++)
{
if (buckets[i][j] != NULL)
{
*(p + k) = buckets[i][j];
buckets[i][j] = NULL;
k++;
}
}
}
}

int main()
{
int a[] = { 73, 22, 93, 43, 55, 14, 28, 65, 39, 81 };//{ 2, 343, 342, 1, 123, 43, 4343, 433, 687, 654, 3 };//
int *a_p = a;
int i;
//计算数组长度
int size = sizeof(a) / sizeof(int);
printf("原始数据:\n");
for (i = 0; i < size; i++)
{
printf("%d\t", a[i]);
}
printf("\n\n");
//基数排序
bucketSort3(a_p, size);
//打印排序后结果

printf("\n返回结果:\n");
for (i = 0; i < size; i++)
{
printf("%d\t", a[i]);
}
printf("\n");
}

运行结果