完全参考了算法导论 第九章 《中位数和统计学》
概述：中位数问题／选择问题
数组的个数为奇数时，中位数惟一，个数为偶数时，中位数为中间两个，这里为了讨论的简单，下文提到的中位数就是值小的中位数。我们还假设数组中元素值都是不同的。所以问题可以变成如下描述：
数组（下标从1开始）元素各不相同，输出第i小的元素
很显然我们可以利用排序在O(n*logn)时间内解出，但实际上会有更加高效的算法。
9.1 最大值或者最小值问题
我们知道求数组中最小或者最大值需要进行n-1次比较，复杂度是O(n)，但是如果需要同时求最大和最小值，直观的做法每个数字都要跟最大值和最小值比较，总共需要进行2*(n - 1)次比较，但是并不是最优的，一种更优的做法是 将原数组中的每相邻两个数为一组，每组数先比较一次，可以得到较小值和较大值，然后用较小值更新全局最小，用较大值更新全局最大，所以每组数进行3次比较，总共比较次数是3 * ceil(n / 2)
练习题9.1-1 求数组中次大数，证明最坏情况的比较次数是
n + ceil(lgn) - 2
9.2 期望线性时间的选择问题
这里利用了快速排序的思想，快速排序中会根据枢轴元素将元素分为两部分，然后每个部分分别进行快排，但在求元素选择问题中，只需要利用一边，如果每次划分的近似均匀一半，那么由主定理可知复杂度是O(n)，以下是随机化选择算法的伪代码：
此算法经过证明在平均意义上复杂度是O(n)(证明过程可以参考书中9.2的详细过程)，但是在最坏情况下可以达到O(n^2)，比如数组基本有序，想找数组中最小的数，每次pivot都选最大的。
9.3 最差情况线性算法
书中给了我们了算法，算法名称是SELECT，找出n个无序元素中的第i小元素，并假设n>1，没有重复元素，步骤如下：
- 将元素分成
floor(n/5)组（每组有5个元素）和剩余一组。 - 将每组元素进行插入排序，然后取出每组元素的中位数。
- 将第二部选择出的中位数递归调用本算法找出其中位数x。
- 将x做为快速排序partition的枢轴元素，对数组进行划分，设定比x小的元素有
k-1个，比x大的元素有n-k个。 - 根据i跟k的关系递归调用本算法。
该算法的证明过程不在这里细说，在最坏情况下仍能保证复杂度是O(n)
数组第k大元素的常见算法可以看下这篇博客
解法1： 我们可以对这个乱序数组按照从大到小先行排序，然后取出前k大，总的时间复杂度为O(n*logn + k)。
解法2： 利用选择排序或交互排序，K次选择后即可得到第k大的数。总的时间复杂度为O(n*k)
解法3： 利用快速排序的思想，从数组S中随机找出一个元素X，把数组分为两部分Sa和Sb。Sa中的元素大于等于X，Sb中元素小于X。这时有两种情况：
- Sa中元素的个数小于k，则Sb中的第k-|Sa|个元素即为第k大数；
- Sa中元素的个数大于等于k，则返回Sa中的第k大数。时间复杂度近似为
O(n)
解法4： 二分[Smin,Smax]查找结果X，统计X在数组中出现，且整个数组中比X大的数目为k-1的数即为第k大数。时间复杂度平均情况为O(n*logn)
解法5：用O(4*n)的方法对原数组建最大堆，然后pop出k次即可。时间复杂度为O(4*n + k*logn)
解法6：维护一个k大小的最小堆，对于数组中的每一个元素判断与堆顶的大小，若堆顶较大，则不管，否则，弹出堆顶，将当前值插入到堆中。时间复杂度O(n * logk)
解法7：利用hash保存数组中元素Si出现的次数，利用计数排序的思想，线性从大到小扫描过程中，前面有k-1个数则为第k大数，平均情况下时间复杂度O(n)