桶排序，海量数据哪里逃？

大家好，我是道哥。今天，我们不聊饭桶，也不聊水桶，而是来聊重要的桶排序，我们先来看一个经典的问题。

武林大会

武林人员的武功值都在[0, 100]之间，具体值如下所示。试对他们的武功值进行排序。

他们的长相如下，女的伶俐，男的英俊：

如果用传统的排序算法，难免会出现一些无用的滑稽比较，比如：

很明显，黄蓉和洪七公不是同一个段位的，没有必要进行比较。欧阳锋和欧阳克也不是同一个段位的，也没有必要进行比较。因此，我们需要优化武功的比较流程。

图解桶排序

怎么优化武功的比较流程呢？可以考虑分段位进行比较。如下，分三个桶，对应不同的段位区间。

显而易见，六个人被划分到对应的桶中，归宿如下：

然后，每个桶内进行排序，得到的结果为：

显然，第一个桶全部小于第二个桶，第二个桶全部小于第三个桶，而每个桶内已经排序好了，所以最终的排序就出来了，如下：

这种排序，就是所谓的桶排序。思路很简单，也很巧妙。

桶排序分析

那么，桶排序有什么好处呢？从直观上来讲，桶排序避免了一些无用的比较。接下来，我们来大致分析一下。

假设桶的个数为M, 平均每个桶内的元素个数为N/M, 桶内排序采用快速排序，所以整个过程的时间复杂度是:

O(N + M*N/Mlog(N/M))

当桶的个数足够多时，M接近于N，上式近似简化为O(N)，也就是说，此时桶排序是线性时间复杂度的排序。

当M=1时，只有一个桶，此时桶排序退化为快速排序，时间复杂度为O(NlogN). 因此，要合理选择桶的个数。

桶排序应用

桶排序可以解决海量数据的排序问题，比如：

有10亿个浮点数，数值在[0, 100000]区间内几乎均匀分布，内存有限的条件下，该如何排序呢？

很显然，由于内存有限，又是海量数据，所以没法把所有的数据一次加载到内存中，一些常规的排序方法无法达到排序目的。

我们可以划分足够的桶，每个桶就是一个文件，然后对每个文件内的数据进行排序(内存足够容纳)，又因为每个文件之间有大小关系，所以直接把所有的文件合并即可，示意图如下：

一图胜千言，一目了然。可以看到，桶排序很适合处理海量数据排序问题。

桶的扩展应用

我们已经了解了桶排序的过程，接下来看这样一个问题：

有10亿个浮点数，数值在[0, 100000]区间内几乎均匀分布，内存有限的条件下，该如何求中位数呢？

这是典型的海量数据的中位数问题，在各种笔试面试中也是经常碰到，我们当然可以采用桶排序来处理。

然而，完全不必要如此。目的是找中位数，压根不需要对所有文件桶中的数据进行排序。

比如，由于数据几乎均匀分布，所以中位数不太可能在第一个文件桶中，所以不需要对第一个文件桶内数据进行排序。

根据每个文件桶内实际数据的多少，我们可以计算出中位数在哪个文件桶，然后可以对这个文件桶进行排序一下就行。

桶是一种分而治之的思想，化大为小，在处理海量数据问题时，尤其有优势。我们也会一步一个脚印，争取每篇文章讲清讲透一件事，也希望大家阅读后有所收获，心情愉快。

你好，我是道哥，CSDN前30名，曾混迹于BAT大厂。公众号讲解计算机基础、网络、数据结构、算法、C++、Java、Golang等多方面的编程知识。欢迎点击如下名片关注道哥，感谢点赞和在看支持哦。

朋友，点个“赞”和“在看”鼓励下呗