利用快速排序的分組思路，假設(shè)對(duì)當(dāng)前主元值t,已將數(shù)組分成三個(gè)部分，a[0,m-1]部分都小于t，a[m]等于t,a[m+1,n-1]大于等于t,此時(shí)比較m+1與k,若m+1<k，可知第k個(gè)元素在右半部分，所以將分組區(qū)間的左下標(biāo)改為m+1,同理，若m+1>k，則將分組區(qū)間的右下標(biāo)改為m-1,若是m+1==k,則表示找到了第k個(gè)元素，返回a[m]?？芍@個(gè)算法的時(shí)間復(fù)雜度為O(cn)，其中c為某個(gè)很小的常數(shù)。實(shí)現(xiàn)時(shí)，依賴于分組的方法，有單向分級(jí)與雙向分組，用隨機(jī)生成的百萬個(gè)數(shù)據(jù)進(jìn)行測(cè)試，結(jié)果單向分組的時(shí)間為雙向分組的兩倍。
代碼如下：
#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;
}