9.桶排序
9.1 算法思想
桶排序假设待排序的一组数均匀独立的分布在一个范围中，并将这一范围划分成几个子范围（桶）。然后基于某种映射函数f （ 高效与否的关键就在于这个映射函数的确定 ），将待排序列的关键字 k 映射到第i个桶中 (即桶数组B 的下标i) ，那么该关键字k 就作为 B[i]中的元素。接着将各个桶中的数据分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排） 。然后依次枚举输出 B[0]….B[M] 中的全部内容即完成了一个数组的桶排列。
ps：桶排序可以有很多方法，具体区别在于映射函数、桶、以及桶内排序的方法不同。
由于要构造桶，因此需要额外的空间，空间复杂度为o（n+k），时间复杂度为o（n+k），最好是o(N)，且桶排序是稳定的。
9.2 算法过程
- 设置一个定量的数组当作空桶；（当数字少的时候，可以设置n个桶，只把相等的数放在同一个桶，不过这种方法空桶过多，数字多的时候回消耗极大的空间。数字多的时候可以少设置几个桶，利用映射关系将多个数放在一个桶。） （类似于系统抽样，是指尽可能均匀分布在各个桶里）
- 遍历输入数据，并且把数据映射完之后，一个一个放到对应的桶里去；
- 对每个不是空的桶进行排序；
-
从不是空的桶里把排好序的数据拼接起来。
桶的数量等于待排序元素数量展示，其中范围分别是[0,9),[10,19),……，[90,99)
9.3 python代码
def
bucktetSort
(
numList
,
bucketNum
)
:
if
len
(
numList
)
==
0
or
len
(
numList
)
==
1
:
return
numList
maxNum
=
numList
[
0
]
minNum
=
numList
[
0
]
for
i
in
range
(
1
,
len
(
numList
)
)
:
# 找到最大最小值
if
numList
[
i
]
<
minNum
:
minNum
=
numList
[
i
]
elif
numList
[
i
]
>
maxNum
:
maxNum
=
numList
[
i
]
else
:
continue
bucketSize
=
(
maxNum
-
minNum
+
1
)
//
bucketNum
# 根据桶的数量找到每个桶的范围
buckets
=
[
[
]
for
i
in
range
(
bucketNum
)
]
for
i
in
range
(
len
(
numList
)
)
:
# 将各个数分配到各个桶
buckets
[
(
numList
[
i
]
-
minNum
)
//
bucketSize
]
.
append
(
numList
[
i
]
)
for
i
in
range
(
bucketNum
)
:
# 桶内排序，可以使用各种排序方法
buckets
[
i
]
.
sort
(
)
res
=
[
]
for
i
in
range
(
len
(
buckets
)
)
:
# 分别将各个桶内的数提出来，压入结果
for
j
in
range
(
len
(
buckets
[
i
]
)
)
:
res
.
append
(
buckets
[
i
]
[
j
]
)
return
res
numlist
=
[
11
,
34
,
23
,
56
,
8
,
20
,
66
,
45
,
54
,
87
,
78
]
print
(
bucktetSort
(
numlist
,
5
)
)
# 利用5个桶
# 输出结果为：[8, 11, 20, 23, 34, 45, 54, 56, 66, 78, 87]
