桶排序

排序思想

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

排序实现逻辑

[:broken_heart:内容太饿了，离家出走了…]{.label .danger}

桶排序算法实现

[:broken_heart:内容太饿了，离家出走了…]{.label .danger}

算法评估

• 桶排序的时间复杂度为: $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个，如果还不能，再进行拆分。知道这个文件都可以读入内存为止。

最后

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