博采众长：桶排序

前置知识

阅读本文前，你需要先学习：

• 计数排序

分开排序 vs 整体排序

以最简单的 选择排序 为例，如果我直接对大小为 $n$ 的数组进行选择排序，那么时间复杂度是 $O(n^2)$。

假设我们将待排序数组分成 $k$ 个桶，对于每个桶使用选择排序，那么总的时间复杂度是大于 $O(n^2)$，还是小于 $O(n^2)$？

这其实是一个简单的数学题，假设有个正整数 $n$，且它可以分解为 $n = n_1 + n_2 + \cdots + n_k$，那么 $n^2$ 和 $n_1^2 + n_2^2 + \cdots + n_k^2$ 哪个更大？

有多种思路可以得到答案，我们来看这种几何的思路：

把这个 $n^2$ 想象成一个正方形的面积，而 $n_1^2 + n_2^2 + \cdots + n_k^2$ 是这个大正方形的一条边上的若干小正方形的面积之和，这样就能直观的理解了，显然这些小正方形的面积没有整个正方形的面积大，所以 $n^2 >= n_1^2 + n_2^2 + \cdots + n_k^2$。

由此可知，分开排序的时间复杂度总和是小于整体排序的，这就是保证桶排序算法的数学基础。

基于正方形面积的这个抽象，我们还可以更进一步。当 $k$ 无限大，$n_1, n_2, \cdots, n_k$ 无限小时会怎样？

正方形那条边上的小正方形面值之和越来越小，最终会和那条边融为一体，也就是说 $n_1^2 + n_2^2 + \cdots + n_k^2$ 的值会无限接近 $n$。

以此观之，如果桶排序将待排序元素分配到尽可能多的桶中（$k$ 尽可能大），即每个桶至多只有一个元素时，桶排序就转化成了 计数排序，其复杂度也将降低到 $O(n)$。

即便不能做到每个桶只有一个元素，只要 $k > 1$，桶排序的时间复杂度也会小于 $O(n^2)$，$k$ 越大，时间复杂度越接近 $O(n)$。

反过来，如果取最小值 $k = 1$，那桶排序就完全退化成了选择排序，时间复杂度是 $O(n^2)$。