10.基数排序
10.1 算法思想
基数排序是对桶排序的扩展。
第一类：最低位优先法，简称LSD法：先从最低位开始排序，再对次低位排序，直到对最高位排序后得到一个有序序列；
第二类：最高位优先法，简称MSD法：先从最高位开始排序，再逐个对各分组按次高位进行子排序，循环直到最低位。（位没有数的话，补0）
这里以LSD为例，由于待排序元素每一位上的数字的取值范围是0—9，因此每按照某一位，需要10个桶，这样每一位上相同的数字会分配到一个桶里。
10.2 算法过程
假设有一未排序数组：
3,44,38,5,47,15,36,26,27,2,46,4,19,50,48
首先根据个位数的数值，在遍历数值时将它们分配至编号0到9的桶中：
0：50
1：
2： 2
3： 3
4： 44,4
5： 5,15
6：36,26,46
7：47,27
8：38,48
9：19,
第二步
接下来将这些桶中的数值重新串接起来，成为以下的数列：
50,2,3,44,4,5,15,36,26,46,47,27,38,48,19
接着再进行一次分配，这次是根据十位数来分配：
0：2,3,4,5
1：15,19
2：26,27
3：36,38
4：44,46,47,48
5：50,
6：
7：
8：
9：
第三步
接下来将这些桶子中的数值重新串接起来，成为以下的数列：
2,3,4,5,15,19,26,27,36,38,44,46,47,48,50
这时候整个数列已经排序完毕。
如果排序的对象有三位数以上，则持续进行以上的动作直至最高位数为止。
10.3 python代码
def
getbit
(
num
,
i
)
:
# 获取元素第i位的数
return
(
num
%
(
i
*
10
)
-
(
num
%
i
)
)
//
i
def
getMax
(
numList
)
:
# 获取数组中的最大值
if
len
(
numList
)
==
1
:
return
numList
[
0
]
maxNum
=
numList
[
0
]
for
i
in
range
(
len
(
numList
)
)
:
if
numList
[
i
]
>
maxNum
:
maxNum
=
numList
[
i
]
return
maxNum
def
radixSort
(
numList
)
:
if
len
(
numList
)
==
0
or
len
(
numList
)
==
1
:
return
numList
maxNum
=
getMax
(
numList
)
bitCount
=
0
index
=
1
while
maxNum
//
index
:
bitCount
+=
1
index
*=
10
currentBit
=
1
# 统计一下最大值的bitCount（有多少位），因为比较多少次，是有最大值的位数决定的
while
currentBit
<=
10
**
(
bitCount
-
1
)
:
# 开始循环的进行每一个位的比较
res
=
[
]
buckets
=
[
[
]
for
i
in
range
(
10
)
]
# 桶排序
for
i
in
numList
:
currentBitNum
=
getbit
(
i
,
currentBit
)
buckets
[
currentBitNum
]
.
append
(
i
)
for
i
in
range
(
10
)
:
for
j
in
range
(
len
(
buckets
[
i
]
)
)
:
res
.
append
(
buckets
[
i
]
[
j
]
)
numList
=
res
currentBit
*=
10
return
numList
numlist
=
[
12
,
3
,
45
,
3543
,
214
,
1
,
4553
]
print
(
radixSort
(
numlist
)
)
# 输出结果为：[1, 3, 12, 45, 214, 3543, 4553]
