【千锤百炼Python—11】：十大排序算法之桶排序

**

**

桶排序是排序算法系列的第十个要介绍的算法，也是最后一个要介绍的算法！

桶排序既属于非比较类排序也属于外部排序。

参考：

https://www.cnblogs.com/onepixel/articles/7674659.html
https://www.runoob.com/w3cnote/bucket-sort.html

桶排序（Counting Sort）是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：

1. 在额外空间充足的情况下，尽量增大桶的数量；
2. 使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中。

同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。

桶排序的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。

• 步骤一：设置一个定量的数组当作空桶；
• 步骤二：遍历输入数据，并且把数据一个一个放到对应的桶里去；
• 步骤三：对每个不是空的桶进行排序；
• 步骤四：从不是空的桶里把排好序的数据拼接起来。

元素分布在桶中：

元素在每个桶中排序：

def bucketsort(array):
    # 选择一个最大的数
    max_num = max(array)
    # 创建一个元素全是0的列表, 当做桶
    bucket = [0] * (max_num + 1)
    # 把所有元素放入桶中, 即把对应元素个数加一
    for i in array:
        bucket[i] += 1

    # 存储排序好的元素
    sort_nums = []
    # 取出桶中的元素
    for j in range(len(bucket)):
        if bucket[j] != 0:
            for y in range(bucket[j]):
                sort_nums.append(j)

    return sort_nums

if __name__ == '__main__':
    array = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
    print(bucketsort(array))

输出结果为：

[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]