// 給一個數組a[n]求其中 第k大的數值的算法
// 基本的思想就是 使用quicksort的一個變種
// 每次進行完part后 判斷它的返回值 是否為k
// 如果為k 返回
// 如果大于k 則在返回的位置的前面找
// 如果小于k 則在返回的位置的后面找

int part(int* a, int start, int end)
{
    int t = a[end-1];
    int e = -2;
    while(start < e)
    {
        while(a[start]<t) start++;
        while(a[e]>t) e--;
        int tmp = a[e];
        a[e] = a[start];
        a[start] = tmp;
    }
    return start;
}



int findK(int* a, int start, int end, int k)
{
    int i = part(a, start, end);
    int rtn;

    if(i < k-1)
    {
        rtn = findK(a, i+1, end);
    }

    else if(i > k-1)
    {
        rtn = findK(a, start, i-1);
    }
    else
    {
        rtn = a[i];
    }

    return rtn;
}