用O(nlgk)时间查找k分位数

思考过程：

      开始我的想法是，既然是已排序的集合，那么我就写一个循环for(i=n/k;i<n;i+=n/k) cout<<A[i]<<" " n/k代表k个集合中的每个集合大小为n/k个元素。每隔n/k个元素就输出一个数，这样循环k-1次就输出了k-1和顺序统计量也就是k分位数。这样时间复杂度就是O(k)，显然比O(nlgk)小，但是题目又要求给出O(nlgk)的算法。我想这可能是翻译有误，”sorted“在这句话里翻译成“已排序”是否妥当？，如果改成原数组初始未排序。那么如果还按照刚才的算法，明显不能求出。然后我就想出另外一个超级简单的算法。利用书中9.3节给出的线性时间求第i小元素的函数SELECT。还是for(i=n/k;i<n;i+=n/k)循环里面循环调用SELECT函数求出第n/k,第2n/k,....第(n-1)n/k小元素不就求出了k分位数？但是仔细研究下其中的时间复杂度发现 O((k-1)n)明显要比O(nlgk)大，所以此算法不可取。

      最后正确的算法是利用类似二分法进行查找选择。为什么说是类似二分法呢？ 因为传统的二分法是一直取一半进行划分，而这里的近似二分法是k=偶数时，当然就是原来的二分法。而k=奇数时，选择近似二分法，就是选取k/2附近的整数进行划分。比如k=7，那么k/2=3.5 所以递归的低区就是k=3等分，高区就是k=4等分。这样可以看成一颗递归树，从根到叶子是一个不断递归找k等分直到到叶子这一层找到全部的k-1个顺序统计量为止。次递归树的高度是2^h=k => h=lgk.而树的每层都经过了最多O(n)时间的SELECT函数的查找，所以总的时间就是O(nlgk)。

代码如下：

[cpp] view plaincopyprint?

1. #include <iostream>  
2. #include <time.h>  
3. using namespace std;  
4. const n=16;//想取多少个元素可自己调整。  
5. int t;  
6. //创建一个装有数组A以每5个元素为1组共n/5组，每组的中位数放入到数组B中，组成一组含有n/5个中位数的数组B  
7. int Find(int A[n],int p,int r);//递归当前数组A中从p到r个元素，以找到辅助中位数数组B的中位数。  
8. int PARTITION(int A[],int p,int r,int t)//t代表中位数数组B中的中位数，这里t代表为主元。  
9. {  
10.     int i=p-1,k=0;  
11.     for (int j=p;j<=r;j++)  
12.     {  
13.         if (A[j]<t)//将比主元t大的元素交换到数组A的右边去，比主元t小的到数组A的左边。  
14.         {  
15.             i++;  
16.             swap(A[i],A[j]);  
17.         }  
18.         if (A[j]==t)//如果A[j]等于主元  
19.         {  
20.             k=j;//那么记录下主元在A中的位置。  
21.         }  
22.     }  
23.     swap(A[i+1],A[k]);//完成划分操作，主元左边的元素都小于主元，主元右边的元素都大于主元。  
24.     return i+1;  
25. }  
26. int SELECT(int A[],int p,int r,int i)//i表示第i小的数。  
27. {  
28.     if (p>=r)  
29.     {  
30.         return A[p];  
31.     }  
32.     int t=Find(A,p,r);//返回的t代表辅助数组B的中位数。      
33.     int q=PARTITION(A,p,r,t);  
34.     int k=q-p+1;  
35.     if (i==k)  
36.     {  
37.         return A[q];  
38.     }  
39.     else if(i<k)  
40.     {  
41.         return SELECT(A,p,q-1,i);  
42.     }  
43.     else return SELECT(A,q+1,r,i-k);  
44. }  
45. int Find(int A[n],int p,int r)  
46. {      
47.     int key=0,t=0,m=r-p+1,h=0;  
48.     if (m%5==0)//如果当前数组A的大小能被5整除，那么这以5个元素为一组的m/5组数，没有余数那一组  
49.     {  
50.         h=m/5;  
51.     }  
52.     else//否则，应该加上含有余数的那一组。  
53.     {  
54.         h=m/5+1;  
55.      }  
56.     int *B=new int[h];  
57.     for(int j=0;j<h;j++)  
58.     {  
59.         B[j]=0;  
60.     }  
61.     for (int k=0;k<h;k++)//5个数一组，共h组。进行插入排序。  
62.     {//经过最多h=n/5+1次循环，那么总共循环了25h=25(n/5+1)=5n+25=O(n)次  
63.         for (int j=t+1+p;j<=5+t+p&&j!=r+2;j++)//h组中每组进行插入排序。注意加上数组初始坐标p(当前数组A的初值坐标)+t(在p基础上每5个为1组)  
64.         {//运行时间分析：5个一组运行插入排序，每次插入排序需要的时间是O(n^2)=5^2=25是基于固定划分的固定常数  
65.             key=A[j-1];  
66.             int i=j-1;  
67.             while (i>t+p&&A[i-1]<key)  
68.             {  
69.                 A[i]=A[i-1];  
70.                 i=i-1;  
71.             }  
72.             A[i]=key;  
73.         }  
74.         t+=5;//进入下一个5个元素为一组的插入排序  
75.     }  
76.     k=0;  
77.     for (int i=0;i<h&&k<h;i++)//经过最多h=n/5+1次循环(O(n))，将当前数组A中的每组的中位数依次放入到B中  
78.     {  
79.         if (i<h-1)  
80.         {  
81.             B[k]=A[2+5*i+p];  
82.             k++;  
83.             continue;  
84.         }  
85.         if(m%5!=0)  
86.         {  
87.             B[k]=A[5*i+p+(m%5)/2];  
88.         }  
89.         else   
90.         {  
91.             B[k]=A[2+5*i+p];  
92.             k++;  
93.         }  
94.     }  
95.     if (h==1)  
96.     {  
97.        return B[0];//当辅助数组B只剩下一个数时，那么这个数就是中位数的中位数。  
98.     }  
99.     else  
100.     {  
101.        return SELECT(B,0,h-1,(h-1)/2+1);//如果数组B元素个数是偶数，那么取数组B中的较小值。  
102.     }  
103. }  
104. void The_kth_quantile(int A[],int B[],int p,int r,int k)//k代表要分成多少元素个数相等的集合。  
105. {  
106.     static j=0;  
107.     if (r-p+1>t)//这k个集合中每个集合有n/k个元素。  
108.     {  
109.         if (k%2!=0)//奇等分时。  
110.         {    
111.             int i=((r-p+1)/k)*((k-1)/2);//对当前数组进行近似二分法，例如k=5 2:3 i=2n/5 n=r-p+1  
112.             int h=SELECT(A,p,r,i);//第i小元素就是数组中A[i-1]  
113.             B[j]=h;j++;  
114.             The_kth_quantile(A,B,p,i-1+p,(k-1)/2);  
115.             The_kth_quantile(A,B,i+p,r,(k+1)/2);  
116.         }  
117.         else//偶等分时。  
118.         {  
119.             int i=((r-p+1)/k)*(k/2);//对当前数组进行二分法  
120.             int h=SELECT(A,p,r,i);  
121.             B[j]=h;j++;  
122.             The_kth_quantile(A,B,p,i-1+p,k/2);  
123.             The_kth_quantile(A,B,i+p,r,k/2);  
124.         }  
125.     }  
126. }  
127. void main()   
128. {  
129.     int k=0;  
130.     int A[n]={0};  
131.     //随机输入数组  
132.     srand( (unsigned)time( NULL ) );  
133.     cout<<"原数组："<<endl;  
134.     for (int i=0;i<n;i++)  
135.     {  
136.         A[i]=rand()%100;  
137.         cout<<A[i]<<"\t";  
138.     }  
139.     cout<<endl;  
140.     cout<<"请输入需要划分的k等份=";  
141.     cin>>k;  
142.     cout<<endl;  
143.     int*B=new int[k+1];  
144.     for (i=0;i<k+1;i++)  
145.     {  
146.         B[i]=0;  
147.     }  
148.     t=n/k;  
149.     if (n%k)  
150.     {  
151.         cout<<"不存在k分位数！"<<endl;  
152.     }  
153.     else  
154.     {  
155.         The_kth_quantile(A,B,0,n-1,k);  
156.     }  
157.     for (i=0;i<k-1;i++)  
158.     {  
159.         cout<<B[i]<<" ";  
160.     }  
161.     cout<<endl;  
162. }