c++快排思想查找第k小数……注意是小RT给定一个大小为n的数组s和一个整数K，请找出数组中的第K小元素。这是一个补充程序的试题，你需要完成一个函数：intfindKth(int*s,intn,

Question

c++ 快排思想查找第k小数……注意是小
RT　
给定一个大小为n的数组s和一个整数K，请找出数组中的第K小元素。
　　这是一个补充程序的试题，你需要完成一个函数：
　　int findKth(int *s, int n, int K)
　　表示在s指向的数组中找到第K小的元素(如果K=1，表示找最小元素)，你需要返回该元素的值。

Answer 1

可以通过改写快速排序算法解决
一趟排序划分出基准位置pivot
1. pivot == k - 1，则pivot 位置数据就是
2. pivot > k - 1，则在左半继续寻找
3. pivot < k - 1，则在右半继续寻找
以下是程序：
int select(int s[ ], int left, int right, int k)
{ // 在s[ left .. right ]中选择第k 小的元素
if (left >= right)
return s[left];
int i = left; // 从左至右的标志
int j = right + 1; // 从右到左的标志
int pivot = s[left]; // 将最左面的元素作为分界数据
while (true)
{
do
{ // 在左侧寻找>= pivot 的元素
i = i + 1;
} while (s[i] < pivot);
do
{ // 在右侧寻找<= pivot 的元素
j = j - 1;
} while (s[j] > pivot);
if (i >= j) // 未发现交换对象
break;
int temp = s[i];
s[i] = s[j];
s[j] = temp;
}
if (j - left + 1 == k)
return pivot;
s[left] = s[j]; // 设置pivot
s[j] = pivot;
if (j - left + 1 < k) // 对一个段递归
return select(s, j + 1, right, k - j - 1 + left);
else
return select(s, left, j - 1, k);
}
int findKth(int *s, int n, int K)
{ // 返回 s[0 .. n - 1]中第K 小的元素
if (K < 1 || K > n)
throw "error";
return select(s, 0, n - 1, K);
}