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