#include <stdio.h>
#define NUM 1001
int a[NUM];
//自定义swap函数 交换x与y的值
void swap(int *x,int *y)
{
int temp;
temp = *x;
*x = *y;
*y = temp;
}
int select(int left, int right, int k)
{
if (left >= right) return a[left];
int i = left; //从左到右的指针
int j = right+1; //从右到左的指针
//最左边元素为分界数
int pivot = a[left];
//左侧>=pivot的元素与右侧<=pivot的元素交换
while (true)
{ //寻找左侧>=pivot的元素
do {
i = i+1;
} while (a[i] < pivot);
//寻找右侧<=pivot的元素
do {
j = j-1;
} while (a[j] > pivot);
if (i >= j) break; //没有发现需要交换的元素 跳出循环
swap(&a[i],&a[j]);
}
//快速排序算法描述中的nleft = j-left
if (j-left+1 == k) return pivot;
a[left] = a[j]; //交换pivot与a[j]
a[j] = pivot; //节点j处划分左右子集
if (j-left+1 < k)
//对一个段进行递归调用
return select(j+1, right, k-j+left-1); //在右子集中查找
else return select(left, j-1, k); //在左子集中查找
}
int main()
{
int n,k;
while (scanf("%d%d",&n,&k))
{
for (int i=0; i<n; i++)
scanf("%d",&a[i]);
printf("%d",select(0,n-1,k));
}
return 0;
}
运行结果
