参考算法导论9.3节的内容和这位大神的博客：http://blog.csdn.net/v_JULY_v上对这一节内容代码的实现进行了学习

尝试实现了以查找中位数为前提的select算法。

算法功能：可以确定一个数组中第k大的元素。

算法思想描述如下：

1、将输入n个元素划分为(n/5：向下取整)个组，每组有5个元素。而只有最后一组为数组剩下的（n mod 5）个元素组成。

2、寻找这些组的中位数：通过对每一个小组进行插入排序，确定中位数。保存到数组mid_arr中。（下标:第i组中位数存在第i位上）

3、对2中查找的中位数数组继续递归调用select函数来查找中位数。

4、最后找到中位数的中位数，记为x。以x为枢纽，对数组进行1次划分，设y为比划分低区元素数目+1。划分以后有(n-y)个元素在高区，x为第y小元素。

5、当k==y时 函数结束，返回x值

         k<y:对低区调用select函数来寻找第k小个数

         k>y:对高区调用select函数来寻找第（k-y）小个元素。k-y是因为已知了y个元素比高区元素小。

具体实现与注释见代码

1 #include
     
       2 #include
      
        3 using namespace std; 4 const int num=21; 5 const int numdev=num/5+1;//向上取整 6 int arr[num]; 7 int mid_arr[numdev]; 8  9 void insert_sort(int arr[],int left,int r)10 {11     for(int i=left; i
       
        left&&arr[j]>key)16         {17             arr[j+1]=arr[j];18             j--;19         }20         arr[j+1]=key;21     }22 }23 int find_mid(int arr[],int left,int right)24 {25     if(left==right) return arr[left];26 27     int index;28     for(index=left; index
        
         0)39     {40         insert_sort(arr,index,remain_num-1);41         int number=index-left;42         mid_arr[number/5]=arr[index+remain_num/2];43     }44 45     int num_group=(right-left)/5-1;46     if((right-left)%5!=0) num_group++;47 48     if(num_group==0) return mid_arr[0];49     else return find_mid(mid_arr,0,num_group);50 }51 52 int find_mid_index(int arr[],int left,int right,int mid)//寻找中位数的位置53 {54     for(int i=left; i<=right; i++)55     {56         if(arr[i]==mid) return i;57     }58     return -1;59 }60 int quick_select(int arr[],int left,int right,int k)61 {62     int mid=find_mid(arr,left,right);63 64     int index=find_mid_index(arr,left,right,mid);65     swap(arr[index],arr[right]);66     int pivot=arr[right];67 68     int i=left;69     int j=right-1;70     //按中位数的中位数对数组进行1次划分。71     while(1)72     {73         while(arr[i]
         
          pivot) j--;75         if(i
          
           k) return quick_select(arr,left,i-1,k);84 else return quick_select(arr,i+1,right,k-m);85 86 }87 int main()88 {89 int arr[num]= { 1,5,9,7,8,4,6,3,2,10,15,13,12,17,18,14,19,21,20,11,16};90 int k=7;91 int ans=quick_select(arr,0,num-1,k);92 cout<
           
            <