桶排序 - 数据结构与算法 | 方家小白 = 和你一起遇见更好的自己

# 排序思想

把将要排序的数据分到几个有序的桶里，每个同理的数据再单独进行排序，桶内拍完序之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了.

# 排序实现逻辑

💔内容太饿了，离家出走了…

# 桶排序算法实现

💔内容太饿了，离家出走了…

# 算法评估

桶排序的时间复杂度为: $O(n)$
桶排序不是稳定的排序算法

# 时间复杂度分析

如果要排序的数据有 n 个，我们把它们均匀的分到 m 个桶内，每个桶里就有 k=n/m 个元素，每个桶内部使用快速排序，时间复杂度为 $O(k*logk)$ 。 m 个桶排序的时间复杂度就是 $O(m*k*logk)$ . 因为 $k = n / m$ , 所以整个桶排序的时间复杂度就是 $O(n*log{\frac{n}{m}}$ ). 当桶的个数 m 接近数据个数 n 时， $log\frac{n}{m}$ 就是一个非常小的常量，这个时候，桶排序的时间复杂度接近 $O(n)$

桶排序的对排序数据的要求非常苛刻。

要排序的数据要很容易就能划分为 m 个桶，并且桶与桶之间要有着天然的大小顺序.
数据要在各个同之间的分布时比较均匀的。如果经过桶的划分之后，有些桶里的数据非常多，有些非常少，很不均匀，那桶内数据排序的时间复杂度就不是一个常量级了。在极端的情况下，所有的数据都被划分到一个桶里，那就退化为 $O(logn)$ 的排序算法了.

桶排序比较适合永载外部排序中。所谓的外部排序就是数据存储在外部磁盘中，数据量比较大，内存有限，无法把数据全部加载到内存中。下面说一个例子

# 桶排序的应用场景

假如我们有 10GB 的订单数据，我们希望按照订单的金额进行排序，可是内存有限，只有几百 MB, 怎么进行排序呢？

我们可以先扫描一遍文件，看订单金额所在的数据范围。假设扫描完毕之后，我们最小的金额是 1 元，最大的时 10 万元，我们将其分为 100 个桶，第一个存 1-1000 元，第二个存 1000-2000，并且，每个桶要按照金额大小命名 (00,01,02…)，依次对每个桶，进行排序就好了.

如果，这个 10GB 的数据是分布不均匀的，就会造成某些文件特大。我们还可以对大的文件进行拆分。继续讲这个区间的文件拆成 100 个，如果还不能，再进行拆分。知道这个文件都可以读入内存为止。

# 最后

期望与你一起遇见更好的自己

算法数据结构与算法排序桶排序线性思想排序