Python实现桶排序
一、桶排序简介
桶排序(Bucket sort)是一种通过分桶和合并实现的排序算法,又被称为箱排序。
桶排序先将数据分到有限数量的桶里,然后对每一个桶内的数据进行排序(桶内排序可以使用任何一种排序算法,如快速排序),最后将所有排好序的桶合并成一个有序序列,列表排序完成。
桶排序需要占用很多额外的空间,对桶内数据进行排序,选择哪种排序算法对于性能的影响至关重要。桶排序适用的场景并不多,用得多一点的是基于桶排序思想的计数排序和基数排序。
二、桶排序原理
桶排序的原理如下:
1. 求出待排序列表中的最大值和最小值,得到数据的范围。
2. 根据数据的范围,选择一个适合的值构建有限数量的桶,确定每个桶的数据范围。如数据范围是[0,100),将数据分成10个桶,第一个桶为[0,10),第二个桶为[10,20),以此类推。
3. 将待排序列表中的数据分配到对应的桶中。
4. 对每一个桶内的数据进行排序,这里可以采用任意一种排序算法,建议采用时间复杂度小的排序算法。
5. 将所有桶中的数据依次取出,添加到一个新的有序序列中,列表排序完成。
以列表 [5, 7, 3, 7, 2, 3, 2, 5, 9, 5, 7, 8] 进行升序排列为例。列表的初始状态如下图。
1. 求出待排序列表中的最大值和最小值,选择一个值来分配桶的数量。例子中的最大值为9,最小值为2,分配三个桶。
2. 走访待排序列表,依次将每一个数据分配到对应的桶中。5属于第二个桶的范围,放到第二个桶中。
3. 继续走访待排序列表,进行分桶。7属于第二个桶的范围,放到第二个桶中。
4. 继续走访待排序列表,进行分桶。3属于第一个桶的范围,放到第一个桶中。
5. 继续走访待排序列表,进行分桶。7属于第二个桶的范围,放到第二个桶中。
6. 一直走访完整个待排序列表,将所有数据都放到对应的桶中。
7. 对每一个桶内的数据进行桶内排序,需要对待排序列表升序排序,所以每个桶内都进行升序排序。
8. 依次取出所有桶中的数据,添加到已排序序列中。先取出第一个桶中的数据,2,2,3,3 。
9. 继续取出第二个桶中的数据,5,5,5,7,7,7 。
10. 继续将所有桶中的数据都取出,添加到已排序序列中,列表排序完成。排序结果如下图。
三、Python实现桶排序
# coding=utf-8
def bucket_sort(array):
min_num, max_num = min(array), max(array)
bucket_num = (max_num-min_num)//3 + 1
buckets = [[] for _ in range(int(bucket_num))]
for num in array:
buckets[int((num-min_num)//3)].append(num)
new_array = list()
for i in buckets:
for j in sorted(i):
new_array.append(j)
return new_array
if __name__ == '__main__':
array = [5, 7, 3, 7, 2, 3, 2, 5, 9, 5, 7, 8]
print(bucket_sort(array))
运行结果:
[2, 2, 3, 3, 5, 5, 5, 7, 7, 7, 8, 9]
代码中,使用Python内置函数max()和min()求出了待排序列表中的最大值和最小值。然后设定每个桶的数据范围为3,创建出三个桶,再将数据添加到对应的桶中。取出每一个桶,对每个桶内的数据都进行排序,代码中直接使用了Python的内置函数sorted(),这里也可以使用快速排序等排序算法。桶内的数据排好序之后,依次将每一个桶中的数据添加到一个有序序列中,列表排序完成。
代码中的 i 表示第 i 个桶,j 表示对桶内数据排序后的第 j 个数据。
四、桶排序的时间复杂度和稳定性
1. 时间复杂度
在桶排序中,需要走访待排序列表中的每一个元素,进行分桶,列表长度为 n ,然后需要对每一个桶进行桶内排序,单个桶内排序的最坏时间复杂度是 O(ni^2),ni 表示第 i 个桶内有 ni 个数据,一共有 k 个桶,时间复杂度为n加每一个桶内排序的时间复杂度,最坏情况下所有数据全被分到了一个桶内,ni=n,时间复杂度为T(n)=n+n^2,再乘分桶和排序的步骤数(常数,不影响大O记法),所以桶排序的时间复杂度为 O(n^2) 。
桶排序的最优情况是将数据均匀地分配到每一个桶中,此时有k个桶,每个桶内有n/k个数据,每个桶内排序的平均时间复杂度为O(n/k*logn/k),整个桶排序的时间复杂度为T(n)=n+k*n/k*logn/k,而当k=n时,即每个桶内只有一个元素(不需要进行桶内排序),时间复杂度为O(n)。
2. 稳定性
根据桶排序的排序原理,会将待排序列表进行分桶、桶内排序和合并。在对每一个桶进行桶内排序时,可以采用不同的排序算法,有些排序算法是稳定的,有些排序算法是不稳定,这会影响到桶排序的稳定性。所以桶排序的稳定性取决于桶内排序算法的稳定性。