利用快速排序的分组思路，假设对当前主元值t,已将数组分成三个部分，a[0,m-1]部分都小于t，a[m]等于t,a[m+1,n-1]大于等于t,此时比较m+1与k,若m+1<k，可知第k个元素在右半部分，所以将分组区间的左下标改为m+1,同理，若m+1>k，则将分组区间的右下标改为m-1,若是m+1==k,则表示找到了第k个元素，返回a[m]。可知这个算法的时间复杂度为O(cn)，其中c为某个很小的常数。实现时，依赖于分组的方法，有单向分级与双向分组，用随机生成的百万个数据进行测试，结果单向分组的时间为双向分组的两倍。
代码如下：
#include<stdio.h>
#include<time.h>
#define MAX 1000001
int n,k;
int h[MAX];
int search1()
{
int l,r,i,m,t,temp;
for(l=0,r=n-1;;)
{
t=h[l];
m=l;
for(i=l+1;i<=r;++i)
if(h[i]<t)
{
temp=h[i];
h[i]=h[++m];
h[m]=temp;
}
h[l]=h[m];
h[m]=t;
if(m+1<k) l=m+1;
else if(m+1>k) r=m-1;
else break;
}
return h[m];
}
int search()
{
int l,r,i,j,t,temp;
for(l=0,r=n-1;;)
{
t=h[l];
i=l,j=r+1;
while(1)
{
do{
i++;
}while(i<=r&&h[i]<t);
do{
j--;
}while(j>=l+1&&h[j]>=t);
if(i>j)
break;
else
{
temp=h[i];
h[i]=h[j];
h[j]=temp;
}
}
h[l]=h[j];
h[j]=t;
if(j+1<k)
l=j+1;
else if(j+1>k)
r=j-1;
else break;
}
return h[j];
}
int main()
{
scanf("%d%d",&n,&k);
int i,j;
for(i=0;i<n;++i)
scanf("%d",&h[i]);
time_t start,end;
start=clock();
printf("%d\n",search());
end=clock();
printf("%f\n",((end-start)*1.0)/CLOCKS_PER_SEC);
return 0;
}