求第K大数的递归函数方法

对于求第K大元素，也可以应用到求中位数.

以下也是基于求中位数对该函数进行演示。

主要思路：

先从数组左边扫描，如果发现了比e小的元素则暂停；再从数组右边扫描，遇到大于等于e的元素则暂停。此时左右两个暂停点的元素是错位的，把他们交换一下。然后从左右暂停点开始重复上述步骤，直到左右扫描在中间某处相会。此时相会的位置就是基准e把两个集合分开的位置，把e换到这个位置上，S1中元素就被放在e的左边，S2中的元素就被放在e的右边。

#include <stdio.h>

void Swap(int* x, int* y)
{
    int temp;
    temp = *x;
    *x = *y;
    *y = temp;
}

int FindKthLargest(int S[], int K, int Left, int Right)
{
    int e = S[Left]; //取第一个元素为基准
    int L = Left, R = Right;

    while (1) //将序列中比基准大的一道基准左边，小的移到右边
    {
        while ((Left <= Right) && (e <= S[Left]))
            Left++;
        while ((Left < Right) && (e > S[Right]))
            Right--;
        if (Left < Right)
            Swap(&S[Left], &S[Right]);
        else
            break;
    }
    Swap(&S[Left - 1], &S[L]);                    //将基准换到两集合之间
    if ((Left - L - 1) >= K)                      //（Left-L-1）表示了集合S1的大小
        return FindKthLargest(S, K, L, Left - 2); //在集合S1中查找
    else if ((Left - L - 1) < K - 1)              //在集合S2中查找
        return FindKthLargest(S, K - (Left - L - 1) - 1, Left, R);
    else
        return e; //找到了，返回e
}

int Median(int S[], int N)
{
    return FindKthLargest(S, (N + 1) / 2, 0, N - 1);
}

int main(void)
{
    int a[] = { 3, 5, 4, 7, 2, 1, 6 };//示例数组
    int i;
    i = Median(a, 7);
    printf("中位数为:%d
", i);
    return 0;
}