桶排序算法 #

1. 桶排序算法介绍
2. 桶排序算法原理
3. 桶排序算法的实现

收获 #

学完本节内容，可以初步理解并掌握桶排序算法。

桶排序算法介绍 #

桶排序(Bucket sort)是一种通过分桶和合并实现的排序算法，又被称为箱排序。

桶排序先将数据分到有限数量的桶里，然后对每一个桶内的数据进行排序(桶内排序可以使用任何一种排序算法，如快速排序)，最后将所有排好序的桶合并成一个有序序列，列表排序完成。

桶排序需要占用很多额外的空间，对桶内数据进行排序，选择哪种排序算法对于性能的影响至关重要。

桶排序算法原理 #

桶排序的原理如下：

1. 求出待排序列表中的最大值和最小值，得到数据的范围。
2. 根据数据的范围，选择一个适合的值构建有限数量的桶，确定每个桶的数据范围。如数据范围是[0,100)，将数据分成10个桶，第一个桶为[0,10)，第二个桶为[10,20)，以此类推。
3. 将待排序列表中的数据分配到对应的桶中。
4. 对每一个桶内的数据进行排序，这里可以采用任意一种排序算法，建议采用时间复杂度小的排序算法。
5. 将所有桶中的数据依次取出，添加到一个新的有序序列中，列表排序完成。

桶排序算法的实现 #

python实现代码如下：

def bucket_sort(a):
    min_num, max_num = min(a), max(a)
    bucket_num = (max_num - min_num) // 3 + 1 #分桶
    buckets = [[] for _ in range(int(bucket_num))]
    for num in a:
        buckets[int((num - min_num) // 3)].append(num)
    new_a = list()
    for i in buckets:
        for j in sorted(i): #采用任意一种排序算法
            new_a.append(j)
    return new_a


if __name__ == '__main__':
    a = [10, 17, 50, 7, 30, 15, 5, 38, 21]
    print(bucket_sort(a))

小结 #

理解并掌握桶排序算法的原理
掌握桶排序的代码实现

习题 #

1. 习题1：画出桶排序算法的流程图
2. 习题2：使用桶排序算法，对列表[10, 17, 50, 7, 30, 24, 27, 45, 15, 5, 36, 21]进行升序排列