寻找第K小的元素

点击链接解释的很棒~~~

//c++版
#include<iostream>
#include<algorithm>
#define Max 100
using namespace std;

int n,k;
int a[Max];
int find(int a[],int low,int high,int k){
        int p=high-low+1;
        if(p<6){                   /*如果要查找的数个数小于6个则直接排序*/ 
            ort(a+low,a+p);
            return a[k-1];
        }
        else{
            int q=p/5;             /*每五个元素分为一组*/
            int remainder = p - q * 5;
            int mid[100];
            for(int i=0;i<q;i++){     /*分别对每组进行排序，取中位数*/
                sort(a+5*i,a+5*(i+1));
                mid[i]=a[i*5+2];
            }
            if(remainder>0){         /*有剩余数则排序取中位数*/
                sort(a+5 * q, a+5 * q + remainder);
                mid[q] = a[q * 5 + (remainder + 1) / 2 - 1];
            }
            int mm=find(mid,0,q-1,(q+1)/2);   /*找中位数集合的中位数*/ 
            int a1[100],a2[100],a3[100];
            int lena1=0,lena2=0,lena3=0;
            /*与中位数集合的中位数进行比较，分成小于、等于、大于三组*/
            for(int i=low;i<=high;i++){    
                if(a[i]<mm)
                    a1[lena1++]=a[i];
                else if(a[i]==mm)
                    a2[lena2++]=a[i];
                else if(a[i]>mm)
                    a3[lena3++]=a[i];
            }
            int lastre = 0;
            /*比中位数集合的中位数小的数字个数大于k,则第k小元素在小于的数组里，仍
然找第k小的数*/
            if (lena1 >= k)         
                lastre = find(a1, 0, lena1 - 1, k);
             /*不大于中位数集合的中位数的数字个数小于k,则第k小元素在大于的数组里，
此时找第k - lena1- lena2小的元素*/
            else if (lena2 + lena1 < k)   
                lastre = find(a3, 0, lena3 - 1, k - lena1- lena2);
            /*第k小的元素等于中位数集合的中位数，则第k小元素在等于于的数组里*/
            else if (lena1 + lena2 >= k)   
                lastre = mm;
            return lastre;
        }
}

int main(){
        while(cin>>n>>k){           /*n为数组大小,k为要找的数的排序*/
            for(int i=0;i<n;i++){
                cin>>a[i];
            }
            if(k>n){
                cout<<"请重新输入¨,\n";
            }
            else{
                int result=find(a,0,n-1,k);
                cout<<"第"<<k<<"小的元素是： "<<result<<";"<<endl;
            }
        }
        return 0;
}