《算法导论》9.3:最坏情况仍为时间复杂度仍为线性的求第k大的数的算法runningdark

这是一个常见面试题，通常的解法也很明显，使用类似快排的思想。

每趟运行，把数组的值分成两部分，一部分比pivot大，一部分比pivot小，因为我们知道pivot在数组中的位置，所以比较k和pivot的位置就知道第k大的值在哪个范围，我们不断的进行recursion,直到pivot就是第k大的值。

《算法导论》9.3章给出了一个最差情况也为线性O(n)的算法。

Step1：把数组划分为若干个子数组，每个子数组里包含5个数，因为会有无法整除的可能，所以最后一个子数组会小于5.

Step2：用插入排序把这5个数排序，然后找出中位数，也就是第3个。

Step3：把获得的中位数又排序，找出中位数的中位数x。如果中位数的个数是偶数，那么取排好序的第m/2个数，m指的是中位数的个数。

Step4：把原来的数组使用类似快排的方法，分成两个部分。一部分比x大，一部分比x小。我们可以假设左边的数大，右边的数小。然后我们可以得到“中位数的中位数”的位置i.

Step5：如果i=k,那么那个“中位数的中位数”就是第k大的数。如果i

T(n)<=T(n/5)+T(7n/10+6)+O(n)

在这章的习题中，基于这个算法，要求证明原先Step1中划分为每组3个和7个的情况的复杂度。7个的情况证明结果和5是一样的。但是对于3的情况，其结果最后可以证明出复杂度并非O(n)。

尝试证明关键步骤如下:

对于划分为3个元素的情况，可以得到递推式(过程略):

T(n)<=T(n/3)+T(2n/3+4)+O(n)

T(n)<=c(n/3)+c(2n/3+4)+an<=cn/3+c+2cn/3+4c+O(n)=cn+5c+an

根据假设，T(n)的最大值是cn,那么又有:

cn+5c+an<=cn

5c+an<=0

显然又a,n>0，那么欲使等式成立，必有c<=0。与我们假设的矛盾。所以我们的假设不成立。

因此，当我们尝试用3划分的时候，该算法的无法在线性复杂度内运行。

这个算法的实现代码比较复杂。对于每组划分5个元素的情况，实现代码如下：