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

求给定输入中第k大的数的算法。

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

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

这个算法的时间预期是O(n)。这里需要注意的是讲的仅限于它的预期，对于这个算法，其在最差情况下，时间复杂度则为n的平法。

参阅快速排序的无敌对手一文，我们是可以构建出一个这样的序列的。最简单的情况，每趟快排的时候我们以第一个为主元，那么对于一个已经排序好的序列，我们要找最大的数，最后的时间花费就退化成了n的平方。

 

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

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

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

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

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

Step 5：如果i = k, 那么那个“中位数的中位数”就是第k大的数。如果 i < k， 不用说，第k大的在x的右边，否则就在左边。递归调用该算法即可。

整个过程中，第1,2,4步所需时间为O(n)， 注意第2步的复杂度不为O(n^2)，第3步的复杂度为 T(n/5)，第五步的复杂度为 T(7n/10)。

注意这里第2步虽然我们使用的是插入排序，但是待排的序列长度为常数5，所以对一组的排序时间花费为O(1),对于n/5个组,其时间预期是O(n/5),即O(n)。

时间预期为：

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

(书中通过数学方法最后推得时间预期是O(n)。因为需要较多的数学准备知识，这里不继续介绍。) 

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

尝试证明关键步骤如下:

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

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

假设存在某个适当大的常数c,使得T(n)<=cn(为什么这样可查阅《算法导论》第一章),用an替代O(n)(因为O(n)代表的这部分的时间花费是线性的，那么必然存在一个常数a,使得an为这部分时间花费)用cn代换掉式中的T(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个元素的情况， 实现代码如下：

/*
 * =====================================================================================
 *
 *       Filename:  okselect.c
 *
 *    Description:
 *
 *        Version:  1.0
 *        Created:  11/14/2012 05:48:58 PM
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  [e-mail] (),
 *   Organization:
 *
 * =====================================================================================
 */
#include <stdlib.h>
#include <stdio.h>
#define swap(a,b) (a)^=(b);(b)^=(a);(a)^=(b)
#define MAX 1000

void sort(int* input, int size){
    printf ( "sort arry size = %d\n", size );
    int i,j;
    for(i = 0; i< size ; i++){
        for(j = 0; j<size-i-1;j++){
            if(input[j]<input[j+1]){
                swap(input[j],input[j+1]);
            }
        }
    }
}
void output(int * input, int size){
    for(;size>0 && *input;size--,input++){
        printf("%d ", *input);
    }
    printf("\n");

}

int partion(int *input, int size, int key){
    printf ( "--------------Step4---------------\n" );
    printf("key = %d \n", input[key]);
    int *head, *tail;
    head = input;
    tail = head + size - 1;
    swap(*head, input[key]);

    int *k = head;
    while(head<tail){
        while(*tail && *k >= *tail){
            tail--;
        }
        if(tail<=head) break;
        swap(*k,*tail);
        k = tail;
        while(*head && *k < *head)
            head++;
        if(head>=tail) break;
        swap(*k,*head);
        k = head;
    }
    output(input, size);
    printf ( "--------------Step4 done--------------\n" );
    return k-input+1;
}

int kselect(int *input, int size, int k){
    printf ( "start element : %d \n", *input );
    if(size<=5){
        sort(input, size);
        return input[k-1];
    }
    int mid[MAX] = {0};
    int midvalue[MAX] = {0};
    int groups = size/5;
    int i;

    printf ( "-----------------step 1, 2--------------\n" );
    for(i = 0; i<groups;i++){
        sort(input+i*5, (i*5+5 > size) ? (size-1):5);
        printf ( "sorted group %d:\n", i );
        output(input+i*5, 5);
        mid[i] = i*5 + 2;
        midvalue[i] = input[i*5 + 2];
    }

    printf ( "-----------------step 1, 2 done--------------\n" );

    printf ( "---------step3-------------\n" );
    sort(midvalue, groups);
    printf ( "---------step3 done-------\n" );
    int m = -1;
    for(i = 0; i<5;i++){
        if(input[mid[i]] == midvalue[groups/2]){
            m = partion(input, size, mid[i]);
        }
    }
    if(m == k){
        return input[m-1];
    }
    if(k<m){
        return kselect(input,m,k);
    }
    else{
        return kselect(input+m, size - m, k-m);
    }
    return 0xffff;
}

int main(){
    int input[] = {1,3,2,10,5,11, 12, 8 ,6, 7};
    int r = kselect(input,sizeof(input)/sizeof(int), 7);
    printf("result %d \n", r);
    return 0;
}