基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的
元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其
时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。
- 中文名
- 基数排序
- 外文名
- Radix sort
- 类 别
- 分配式排序
- 别 称
- “桶子法”
- 方 法
- 最高位优先法和最低位优先
- 发明者
- 赫尔曼·何乐礼
- 领 域
- 计算机算法
基本解法
第一步
以LSD为例，假设原来有一串数值如下所示：
73, 22, 93, 43, 55, 14, 28, 65, 39, 81
首先根据个位数的数值，在走访数值时将它们分配至编号0到9的桶子中：
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
接着再进行一次分配，这次是根据十位数来分配：
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相反，是由高位数为基底开始进行分配，但在分配之后并不马上合并回一个
数组中，而是在每个“桶子”中建立“子桶”，将每个桶子中的数值按照下一数位的值分配到“子桶”中。在进行完最低位数的分配后再合并回单一的
数组中。
效率分析
时间效率
[1] ：设待排序列为n个记录，d个关键码，关键码的取值范围为radix，则进行链式基数排序的
时间复杂度为O(d(n+radix))，其中，一趟分配时间复杂度为O(n)，一趟收集时间复杂度为O(radix)，共进行d趟分配和收集。 空间效率：需要2*radix个指向队列的辅助空间，以及用于
静态链表的n个
指针。
实现方法
最高位优先(Most Significant Digit first)法，简称MSD法：先按k1排序分组，同一组中记录，关键码k1相等，再对各组按k2排序分成子组，之后，对后面的关键码继续这样的排序分组，直到按最次位关键码kd对各子组排序后。再将各组连接起来，便得到一个有序序列。
最低位优先(Least Significant Digit first)法，简称LSD法：先从kd开始排序，再对kd-1进行排序，依次重复，直到对k1排序后便得到一个有序序列。
实现原理
基数排序的发明可以追溯到1887年赫尔曼·何乐礼在打孔卡片制表机(Tabulation Machine)上的贡献。它是这样实现的：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
基数排序的方式可以采用LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。
实现
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
|
#include<math.h>
testBS()
{
inta[] = {2, 343, 342, 1, 123, 43, 4343, 433, 687, 654, 3};
int *a_p = a;
intsize = sizeof(a) / sizeof(int);
bucketSort3(a_p, size);
inti;
for(i = 0; i < size; i++)
{
printf("%d\n", a[i]);
}
intt;
scanf("%d", t);
}
voidbucketSort3(int *p, intn)
{
intmaxNum = findMaxNum(p, n);
intloopTimes = getLoopTimes(maxNum);
inti;
for(i = 1; i <= loopTimes; i++)
{
sort2(p, n, i);
}
}
intgetLoopTimes(intnum)
{
intcount = 1;
inttemp = num / 10;
while(temp != 0)
{
count++;
temp = temp / 10;
}
returncount;
}
intfindMaxNum(int *p, intn)
{
inti;
intmax = 0;
for(i = 0; i < n; i++)
{
if(*(p + i) > max)
{
max = *(p + i);
}
}
returnmax;
}
voidsort2(int *p, intn, intloop)
{
intbuckets[10][20] = {};
inttempNum = (int)pow(10, loop - 1);
inti, j;
for(i = 0; i < n; i++)
{
introw_index = (*(p + i) / tempNum) % 10;
for(j = 0; j < 20; j++)
{
if(buckets[row_index][j] == NULL)
{
buckets[row_index][j] = *(p + i);
break;
}
}
}
intk = 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++;
}
}
}
}
|
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
|
public class RadixSort
{
public static void sort(int[] number, int d)
{
intk = 0;
intn = 1;
intm = 1;
int[][]temp = newint[10][number.length];
int[]order = newint[10];
while(m <= d)
{
for(inti = 0; i < number.length; i++)
{
intlsd = ((number[i] / n) % 10);
temp[lsd][order[lsd]] = number[i];
order[lsd]++;
}
for(inti = 0; i < 10; i++)
{
if(order[i] != 0)
for(intj = 0; j < order[i]; j++)
{
number[k] = temp[i][j];
k++;
}
order[i] = 0;
}
n *= 10;
k = 0;
m++;
}
}
public static void main(String[] args)
{
int[]data =
{73, 22, 93, 43, 55, 14, 28, 65, 39, 81, 33, 100};
RadixSort.sort(data, 3);
for(inti = 0; i < data.length; i++)
{
System.out.print(data[i] + "");
}
}
}
|
pascal
|
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
|
type link=^node;
node=record
data:integer;
next:link;
end;
var
i,j,l,m,k,n:integer;
a:array[1..100] of integer;
s:string;
q,head:array[0..9] of link;
p,p1:link;
begin
readln(n);
writeln('Enterdata:');
for i:=1 to n do read(a[i]);
for i:=5 downto 1 do
begin
for j:=0 to 9 do
begin
new(head[j]);
head[j]^.next:=nil;
q[j]:=head[j]
end;
for j:=1 to n do
begin
str(a[j],s);
for k:=1 to 5-length(s) do
s:='0'+s;
m:=ord(s[i])-48;
new(p);
p^.data:=a[j];
p^.next:=nil;
q[m]^.next:=p;
q[m]:=p;
end;
l:=0;
for j:=0 to 9 do
begin
p:=head[j];
while p^.next<>nil do
begin
l:=l+1;
p1:=p;
p:=p^.next;
dispose(p1);
a[l]:=p^.data;
end;
end;
end;
writeln('Sorteddata:');
for i:=1 to n do
write(a[i]:6);
end.
|
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
|
int maxbit(int data[], int n)
{
int d = 1;
int p = 10;
for(int i = 0; i < n; ++i)
{
while(data[i] >= p)
{
p *= 10;
++d;
}
}
return d;
}
void radixsort(int data[], int n)
{
int d = maxbit(data, n);
int *tmp = newint[n];
int *count = newint[10];
int i, j, k;
int radix = 1;
for(i = 1; i <= d; i++)
{
for(j = 0; j < 10; j++)
count[j] = 0;
for(j = 0; j < n; j++)
{
k = (data[j] / radix) % 10;
count[k]++;
}
for(j = 1; j < 10; j++)
count[j] = count[j - 1] + count[j];
for(j = n - 1; j >= 0; j--)
{
k = (data[j] / radix) % 10;
tmp[count[k] - 1] = data[j];
count[k]--;
}
for(j = 0; j < n; j++)
data[j] = tmp[j];
radix = radix * 10;
}
delete[]tmp;
delete[]count;
}
|
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
120
121
|
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace LearnSort
{
class Program
{
static void Main(string[] args)
{
int[] arr = CreateRandomArray(10);
Print(arr);
RadixSort(refarr);
Print(arr);
Console.ReadKey();
}
public static void RadixSort(ref int[] arr)
{
int iMaxLength = GetMaxLength(arr);
RadixSort(ref arr, iMaxLength);
}
private static void RadixSort(ref int[] arr, int iMaxLength)
{
List<int> list = newList<int>();
List<int>[] listArr = newList<int>[10];
char currnetChar;
string currentItem;
for(int i = 0; i < listArr.Length; i++)
listArr[i] = newList<int>();
for(int i = 0; i < iMaxLength; i++)
{
foreach(int number in arr)
{
currentItem = number.ToString();
try
{
currnetChar = currentItem[currentItem.Length - i - 1];
}
catch
{
listArr[0].Add(number);
continue;
}
switch(currnetChar)
{
case'0':
listArr[0].Add(number);
break;
case'1':
listArr[1].Add(number);
break;
case'2':
listArr[2].Add(number);
break;
case'3':
listArr[3].Add(number);
break;
case'4':
listArr[4].Add(number);
break;
case'5':
listArr[5].Add(number);
break;
case'6':
listArr[6].Add(number);
break;
case'7':
listArr[7].Add(number);
break;
case'8':
listArr[8].Add(number);
break;
case'9':
listArr[9].Add(number);
break;
default:
throw new Exception("unknowerror");
}
}
for(int j = 0; j < listArr.Length; j++)
foreach(int number in listArr[j].ToArray<int>())
{
list.Add(number);
listArr[j].Clear();
}
arr = list.ToArray<int>();
Print(arr);
list.Clear();
}
}
private static int GetMaxLength(int[] arr)
{
int iMaxNumber = Int32.MinValue;
foreach(int i in arr)
{
if(i > iMaxNumber)
iMaxNumber = i;
}
return iMaxNumber.ToString().Length;
}
public static void Print(int[] arr)
{
foreach(intiinarr)
System.Console.Write(i.ToString() + '\t');
System.Console.WriteLine();
}
public static int[] CreateRandomArray(int iLength)
{
int[] arr = new int[iLength];
Random random = new Random();
for(inti = 0; i < iLength; i++)
arr[i] = random.Next(0, 1001);
return arr;
}
}
}
|
python 实现
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
import math
def sort(a, radix=10):
K = int(math.ceil(math.log(max(a), radix)))
bucket = [[] for i in range(radix)]
for i in range(1, K+1):
for val in a:
bucket[val%(radix**i)/(radix**(i-1))].append(val)
del a[:]
for each in bucket:
a.extend(each)
bucket = [[] for i in range(radix)]
|
