算法导论9.3-6
题目：
对一个含有n个元素的集合来说，所谓k分位数（the kth quantile），就是能把已排序的集合分成k个大小相等的集合的k-1个顺序统计量。给出一个能列出某一集合的k分位数的O(nlgk)时间的算法
思路：
每个子集合的元素个数为t = n / k，A[j]是数组A中下标为j的元素，A(j)是数组是第j大的元素
则所求的k分位数是指A(t)，A(2t)，A(3t)，……，A((k-1)t)
常规思路是按照顺序求第t小，第2t小。。。。的元素
按顺序依次求这k-1个数的运行时(k-1)*n
要使运行时间为O(nlgk)，改进方法是不要依次寻找这k-1个数，而是借用二分的方法来找。
先找第k/2个分位数，再以这个分位数为主元把数组分为两段，分别对这两段来找分位数，这个时候找的范围变小了，效率也就提高了
代码如下：
//例题9.2中的算法的期望时间复杂度为O(n)，而在9.3的例题中的最坏运行时间复杂度为O(n)。//该算法实现思路是将数组每五个元素分为一组，最后一组可能不足五个。//选出每一组中的中位数，然后选出这些中位数的中位数。根据这个中位数对数组进行划分为两组。//然后再按照9.。2中的方法递归调用划分寻找第i小的数。//该算法的对比于9.2的改进之处在于对partition方法进行了优化，而不是随进选择数组进行划分。#include<iostream>using namespace std;//插入排序不解释void Insert_sort(int a[],int p,int r) { int i,j,key,length;length=r-p+1; for(i=p+1;i<=r;i++) { key=a[i]; j=i-1; while(key<a[j]) { int temp; temp=a[j+1]; a[j+1]=a[j]; a[j]=temp; j=j-1; if(j<p) { break; } } } } //按照中位数的中位数进行分割int Partition(int a[] ,int p,int r){int i=p,j=0,temp,num,b[100];//将a中每五个元素进行插入排序，并找出五个元素中的中位数放到b中while(1){if(i>r){break;}if((i+4)<=r){Insert_sort(a,i,i+4);b[j++]=a[i+2];}else{Insert_sort(a,i,r);b[j++]=a[(r+i)/2];}i+=5;}j=j-1;//对b中的元素进行排序Insert_sort(b,0,j);//找到b中的中位数num=b[j/2];//将a中的num与a[r]替换for(i=0;i<=r;i++){if(num==a[i])break;}temp=a[i];a[i]=a[r];a[r]=temp;//根据找到的num对数组进行划分j=p-1;for(i=p;i<r;i++){if(a[i]<num){j++;temp=a[i];a[i]=a[j];a[j]=temp;}}temp=a[r];a[r]=a[j+1];a[j+1]=temp;return j+1;}//按照特定的数字num进行分割int Partition1(int a[] ,int p,int r,int num){int i,j=0,temp;//将a中每五个元素进行插入排序，并找出五个元素中的中位数放到b中//将a中的num与a[r]替换for(i=0;i<=r;i++){if(num==a[i])break;}temp=a[i];a[i]=a[r];a[r]=temp;//根据找到的num对数组进行划分j=p-1;for(i=p;i<r;i++){if(a[i]<num){j++;temp=a[i];a[i]=a[j];a[j]=temp;}}temp=a[r];a[r]=a[j+1];a[j+1]=temp;return j+1;}//选择第num小的数字int Select(int a[],int p,int r,int num){if(p==r){return a[p];}int q=Partition(a,p,r);int k=q-p+1;if(k==num){return a[q];}else if(num<k){return Select(a,p,q-1,num);}else{return Select(a,q+1,r,num-k);}}//将从小标为p到r的数组a分割成k个集合，该集合是从n+1个分割数开始的void SelectKthQuantile(int a[],int b[],int p,int r,int k,int n){if(k<=1){return ;}int length,t,s;length=r-p+1;if(length%k!=0){cout<<"不能划分为"<<k<<"个大小相等的集合！"<<endl;return ;}t=length/k;//选择中间的分割数s=Select(a,p,r,(k+1)/2*t);b[n+(k+1)/2]=s;//利用该分割数将数组划分为两部分Partition1(a,p,r,s);//本别对这两部分数组进行查找剩余的分割数SelectKthQuantile(a,b,p,(n+(k+1)/2)*t-1,(k+1)/2,0);SelectKthQuantile(a,b,(n+(k+1)/2)*t,r,k/2,n+(k+1)/2);}int main(){int a[15]={16,48,748,742,1635,2,56,48,685,4596,3,4,1,6,5};int b[100];SelectKthQuantile(a,b,0,14,5,0);for(int i=1;i<5;i++){cout<<b[i]<<" ";}cout<<endl;return 0;}