#include <stdio.h>
#define NUM 1001
int a[NUM];
//自定義swap函數(shù) 交換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; //從右到左的指針
//最左邊元素為分界數(shù)
int pivot = a[left];
//左側(cè)>=pivot的元素與右側(cè)<=pivot的元素交換
while (true)
{ //尋找左側(cè)>=pivot的元素
do {
i = i+1;
} while (a[i] < pivot);
//尋找右側(cè)<=pivot的元素
do {
j = j-1;
} while (a[j] > pivot);
if (i >= j) break; //沒有發(fā)現(xiàn)需要交換的元素 跳出循環(huán)
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; //節(jié)點(diǎn)j處劃分左右子集
if (j-left+1 < k)
//對(duì)一個(gè)段進(jìn)行遞歸調(diào)用
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;
}
運(yùn)行結(jié)果
