1 int select(int num[],int p,int r,int k){
 2     int len=r-p+1;
 3     //当前小于等于五个元素直接排序求第k小 
 4     if(len<=5){
 5         sort(num,num+len);
 6         return num[k-1];
 7     }else{
 8         //将数组分组，五个一组
 9         int group=len/5;
10         int m=len-group*5; //剩下的元素赋值给m
11         rep(i,0,group-1){ //分组排序 
12             sort(num+i*5,num+i*5+5);
13             mid[i]=num[i*5+2];
14         }
15         if(m>0){
16             sort(num+group*5,num+group*5+m);
17             mid[group]=num[group*5+m/2];
18             group++;
19         }
20         sort(mid,mid+group);
21         int mm=mid[group/2];
22         int len1=0,len2=0;
23         //用mm把数组分为s1和s2
24         rep(i,p-1,r-1){
25             if(num[i]<mm){
26                 s1[len1++]=num[i];
27             }else s2[len2++]=num[i];
28         }
29         int ans=0;
30         if(k==len1+1) ans=mm;
31         else if(k<=len1) ans=select(s1,1,len1,k);
32         else ans=select(s2,1,len2,k-len1);
33         return ans;
34     }
35 }