- 基数排序
- 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)
{
//建立一组桶此处的20是预设的根据实际数情况修改
intbuckets[10][20] = {};
//求桶的index的除数
//如798个位桶index=(798/1)%10=8
//十位桶index=(798/10)%10=9
//百位桶index=(798/100)%10=7
//tempNum为上式中的1、10、100
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)
//d表示最大的数有多少位
{
intk =
0
;
intn =
1
;
intm =
1
;
//控制键值排序依据在哪一位
int
[][]temp = newint[
10
][number.length];
//数组的第一维表示可能的余数0-9
int
[]order = newint[
10
];
//数组orderp[i]用来表示该位是i的数的个数
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++)
//进行d次排序
{
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];
//将tmp中的位置依次分配给每个桶
for
(j = n - 1; j >= 0; j--)
//将所有桶中记录依次收集到tmp中
{
k = (data[j] / radix) % 10;
tmp[count[k] - 1] = data[j];
count[k]--;
}
for
(j = 0; j < n; j++)
//将临时数组的内容复制到data中
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;
//存放当前的字符比如说某个元素123中的2
string
currentItem;
//存放当前的元素比如说某个元素123
for
(
int
i = 0; i < listArr.Length; i++)
//给十个桶分配内存初始化。
listArr[i] = newList<
int
>();
for
(
int
i = 0; i < iMaxLength; i++)
//一共执行iMaxLength次，iMaxLength是元素的最大位数。
{
foreach
(
int
number
in
arr)
//分桶
{
currentItem = number.ToString();
//将当前元素转化成字符串
try
{
currnetChar = currentItem[currentItem.Length - i - 1];
//从个位向高位开始分桶
}
catch
{
listArr[0].Add(number);
//如果发生异常，则将该数压入listArr[0]。比如说5是没有十位数的，执行上面的操作肯定会发生越界异常的，这正是期望的行为，我们认为5的十位数是0，所以将它压入listArr[0]的桶里。
continue
;
}
switch
(currnetChar)
//通过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++)
//将十个桶里的数据重新排列，压入list
foreach
(
int
number
in
listArr[j].ToArray<
int
>())
{
list.Add(number);
listArr[j].Clear();
//清空每个桶
}
arr = list.ToArray<
int
>();
//arr指向重新排列的元素
//Console.Write("{0}times:",i);
Print(arr);
//输出一次排列的结果
list.Clear();
//清空list
}
}
//得到最大元素的位数
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();
}
//产生随机数组。随机数的范围是0到1000。参数iLength指产生多少个随机数
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
|
#!/usr/bin/env python
#encoding=utf-8
import
math
def
sort(a, radix
=
10
):
"""a为整数列表， radix为基数"""
K
=
int
(math.ceil(math.log(
max
(a), radix)))
# 用K位数可表示任意整数
bucket
=
[[]
for
i
in
range
(radix)]
# 不能用 [[]]*radix
for
i
in
range
(
1
, K
+
1
):
# K次循环
for
val
in
a:
bucket[val
%
(radix
*
*
i)
/
(radix
*
*
(i
-
1
))].append(val)
# 析取整数第K位数字 （从低到高）
del
a[:]
for
each
in
bucket:
a.extend(each)
# 桶合并
bucket
=
[[]
for
i
in
range
(radix)]
|
