利用快速排序的分組思路，假設對當前主元值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;
}