// 給一個(gè)數(shù)組a[n]求其中 第k大的數(shù)值的算法
// 基本的思想就是 使用quicksort的一個(gè)變種
// 每次進(jìn)行完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;
}