借助刚才的划分算法，我们可以比较容易的求出第K大的数，平均性能为O(N)，最坏可能是O(N^2)。

注意关于idx的选择，随机的话效果会比选left、right和median好，如果数据不是很特殊的化。

#include <stdio.h>

typedef int TYPE;

int cmp(TYPE a, TYPE b)
{
    return a - b;
}

void swap(TYPE* a, TYPE* b)
{
    TYPE tmp;
    tmp = *a;
    *a = *b;
    *b = tmp;
}

int partition(TYPE* arr, int left, int right, int pivotIndex)
{
    //First swap arr[pivotIndexx] and arr[right]
    TYPE pivot = arr[pivotIndex];
    int store, i;
    swap(&arr[pivotIndex], &arr[right]);

    //Scan from left to right
    store = i = left;
    for(;i<right;i++)
    {
        if(cmp(arr[i], pivot)<=0)
        {
            swap(&arr[store], &arr[i]);
            store++;
        }
    }

    //Final swap arr[store] and arr[right](pivot)
    swap(&arr[store], &arr[right]);
    return store;
}

//Return the arr[k]
TYPE kth(TYPE* arr, int left, int right, int k)
{
    //Select the midian and partition the array
    int idx = (left + right) / 2;
    int pivotIndex = partition(arr, left, right, idx);

    if( left + k - 1 == pivotIndex)
    {
        return arr[pivotIndex];
    }

    if( left + k - 1 < pivotIndex)
    {
        return kth(arr, left, pivotIndex - 1, k);
    }

    if( left + k - 1 > pivotIndex)
    {
        return kth(arr, pivotIndex + 1, right, k - (pivotIndex - left +1));
    }
}

int main()
{
    TYPE arr[16] = {15, 9, 8, 1, 4, 11, 7, 12, 13, 6, 5, 3, 16, 2, 10, 14};
    int len = sizeof(arr)/sizeof(TYPE);
    int store;
    int k;

    //partition
    //store = partition(arr, 0, len - 1, 9);
    //printf("Pivot\t%d\n",store);

    //kth
    k = 15;
    printf("%dth\t%d\n",k,kth(arr,0,len-1,k));

    //print
    //int i;
    //for(i=0;i<len;i++)
    //{
    //  printf("%d ",arr[i]);
    //}
    printf("\n");
}

拓展：
HDOJ
Kth number