天空望着大海，一样的颜色

给定数组，求第k大的数。各种方法：

1 排序，O(nlogn)

2 随机划分randonized partition

对随机主元做划分，得到主元的位置后再分治处理。分治法。最坏情况O(n^2)，平均情况O(n)

3 最坏情况的linear算法

先对数据5个一分组，求每一个分组的中位数。

再求median数组的中位数（可递归求，带数据移动），求出中中位数(median of median)的位置。

再分治处理。（需要做数据的移动）

最坏情况为O(n)，空间复杂度O(n)

4  堆排序，准备一个大小为k的小(大)顶堆。顺序遍历数组，在k-堆上做堆调整，最终堆顶元素即为第k元素。

时间复杂度O(nlogk)，空间复杂度O(k)，比较合适k较小的情况。注：对n长的数组建堆的时间是O(n)。

(更新) 5 败者树。败者树是一棵完全二叉树，叶子节点是数据结点，内部结点是比较结点。内部结点留下败者，将胜者向上传递。所以空间是O(2k)。在维护上，败者树从下向上，堆从上向上。败者树一定要维护到头而堆可以到达到一层就不再向上。