简介

桶排序又叫箱排序，工作的原理是将数组分到有限数量的桶子里。

每个桶子再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。桶排序是鸽巢排序的一种归纳结果。

桶排序也是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。

为了使桶排序更加高效，我们需要做到这两点：

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

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

最快情况：当输入的数据可以均匀的分配到每一个桶中；

最慢情况：当输入的数据被分配到了同一个桶中。

稳定性分析

桶排序的稳定性取决于桶内排序使用的算法。

复杂度分析平均时间复杂度：O(n + k)最佳时间复杂度：O(n + k)最差时间复杂度：O(n ^ 2)空间复杂度：O(n * k)稳定性：稳定

桶排序最好情况下使用线性时间O(n)，桶排序的时间复杂度，取决于对各个桶之间数据进行排序的时间复杂度，因为其它部分的时间复杂度都为O(n)。

很明显，桶划分得越小，各个桶之间的数据越少，排序所用的时间也会越少。但相应的空间消耗就会增大。

步骤创建一个定量的数组当作空桶子；遍历序列，把元素一个一个放到对应的桶子去；对每个不是空的桶子进行排序；从不是空的桶子里把元素再放回原来的序列中。图片演示实例代码

##### 今日头条：技术好奇心##### 桶排序def bucket_sort(arr):    # 取数组最大值    max_num = max(arr)    # 取数组长度    n = len(arr)    # 创建n个空桶    buckets = [[] for _ in range(n)]    # 遍历arr    for var in arr:        # i 表示 var 放到几号桶里,        # 这里min是控制不超出范围        i = min(var // (max_num // n), n-1)        # 把 var 加到桶里边        buckets[i].append(var)        # 保持桶内的顺序        for j in range(len(buckets[i])-1, 0, -1):            # 比较相邻元素大小            if buckets[i][j] < buckets[i][j-1]:                # 后面比前面大则进行交换操作                buckets[i][j], buckets[i][j-1] = buckets[i][j-1], buckets[i][j]            else:                break    # 建立返回结果数组    the_arr = []    # 循环提取桶内数据    for buc in buckets:        # 逐个追加合并        the_arr.extend(buc)    # 返回新数组    return the_arrif __name__ == "__main__":    print('今日头条：技术好奇心')    print('----------- 排序前数组内容 -----------------')    arr = [7, 12, 56, 23, 19, 33, 35, 42, 42, 2, 8, 22, 39, 26, 17]    print(arr)    new_arr = bucket_sort(arr)    print('------------ 排序后的结果 ------------------')    print(new_arr)

运行结果：

今日头条：技术好奇心----------- 排序前数组内容 -----------------[7, 12, 56, 23, 19, 33, 35, 42, 42, 2, 8, 22, 39, 26, 17]------------ 排序后的结果 ------------------[2, 7, 8, 12, 17, 19, 22, 23, 26, 33, 35, 39, 42, 42, 56]

相关文章

Python 实现经典算法之快速排序

Python 实现经典算法之选择排序

Python 实现经典算法之插入排序

Python 实现经典算法之堆排序

Python 实现经典算法之计数排序

Python 实现经典算法之冒泡排序

Python 实现经典算法之归并排序

Python 实现经典算法之希尔排序