bucket_sort

Posted on |

bucket sort 总结

桶排序适用情况：输入需要排序的数据在一个范围内均匀分布

例如，对0.0到1.0均匀分布的浮点数进行排序

对于上述问题简单的方法是使用对比排序的方法，对于对比排序算法的下界(merge sort[归并排序]，heap sort[堆排序] ，quick-sort[快排])都是O(nlogn)的时间复杂度，也就是说他们不能比O(nlogn)更好

我们可以用线性的时间完成对上述问题进行排序吗？ 计数排序不能在这个问题中使用因为我们用每个参与排序的数值作为数组的index， 但是我们这里参与排序的是浮点数。

我们借用类似计数排序的思想，使用桶排序。

下面是桶排序的算法流程：

1
2
3
4
5
6
7
8
9
10
bucket_sort(A)
1 n = A.length
2 let B[0..n-1] be a new array
3 for i = 0 to n-1
4 	make B[i] an empty list
5 for i = 1 to n 
6	insert A[i] to list B[int(nA[i])]
7 for i = 0 to n-1
8	sort listB[i] with insertion sort
9 concatenate this lists B[0]..B[n-1]together in order

时间复杂度：

除了第8行之外，其他各行时间复杂度都是O(n)

分析第8行插入排序的时间复杂度：

$$n_i$$代表桶B[i]的元素个数的随机变量

$$ T(n) = \Theta(n) +\sum_{i=0}^{n-1}O(n_i^2) $$

通过对输入数据取期望，可以计算出期望的运行时间。

$$E[T(n)] = E[ \Theta(n) +\sum_{i=0}^{n-1}O(n_i^2)] =\Theta(n) +\sum_{i=0}^{n-1}O(E[n_i^2]) $$

$$E[n_i^2] = 2 - \frac{1}{n}$$

证明：

我们定义指示变量：对所有i=0,1…,n-1和j = 1,2,…,n

$$X_{ij} = I\{A[j]落入桶i\}$$

$$n_i = \sum_{j=1}^nX_{ij}$$

所以

$$E[n_i^2] = E[\sum_{j=1}^n\sum_{k=1}^nX_{ij}X_{ik}] = E[\sum_{j=1}^nX_{ij}^2 + \sum_{1\le j\le n}\sum_{1\le k \le n ^{k\neq j }}X_{ij}X_{ik}] = \sum_{j=1}^nE[X_{ij}^2]+ \sum_{1\le j\le n}\sum_{1\le k \le n ^{k\neq j }}E[X_{ij}X_{ik}] $$

$$E[X_{ij}^2] = 1^2 \frac{1}{n} + 0^2 (1-\frac{1}{n}) = \frac{1}{n} $$

当$k\neq j$的时候，随机变量$X_{ij}X_{ik}$是独立的，因此有$E[X_{ij}X_{ik}] = \frac{1}{n^2}$

$$E[n_i^2] = 1 + n(n-1)\frac{1}{n^2}=2-\frac{1}{n}$$

所以$$ E[T(n)] = E[ \Theta(n) +\sum_{i=0}^{n-1}O(n_i^2)] =\Theta(n) +\sum_{i=0}^{n-1}O(E[n_i^2]) =\Theta(n) + n*(2-\frac{1}{n}) = \Theta(n) $$

即使输入数据分布不服从均匀分布，桶排序依然可以在线性时间内完成，只要输入数据满足：所有桶大小的平方和与总的元素数成线性关系

例题：

leetcode

  1. Top K Frequent Elements 前K个高频元素

    将数组长度作为frequency的所有可能来进行桶排序