算法导论-顺序统计(四)
n i;
117 }
118 /*
119 ?* ? ?最坏情况下线性时间选择算法
120 ?* ? ?此算法依然是建立在快速排序的划分算法基础之上的
121 ?* ? ?但是与randomizedSelect算法的不同指之处，就是次算法的本质
122 ?* ? ?是保证了每次划分选择的划分主元一定是一个较好的主元，算法先对数组5个一组进行分组
123 ?* ? ?然后选择每组的中位数，再递归的选择各组中位数中的中位数作为数组的划分主元，以此保证划分的平衡性
124 ?* ? ?选择中位数的时候必须使用递归调用的方法才能降低时间复杂度
125 ?* ? ?从而保证在最坏情况下都得到一个好的划分
126 ?* ? ?最坏情况下时间复杂度为O(n)
127 ?*/
128 template
129 T Select::WorseLinearSelect(vector &A,int p,int q,int k)
130 {
131 ? ? // 将输入数组的n个元素划分为n/5（上取整）组，每组5个元素，
132 ? ? // 且至多只有一个组有剩下的n%5个元素组成。
133 ? ? if (p==q) return A[p];
134?
135 ? ? int len=q-p+1;
136 ? ? int medianCount=1;
137 ? ? if (len>5)
138 ? ? ? ? medianCount = len%5 >0 ? len/5 + 1 : len/5;
139 ? ? vector medians(medianCount);//存放每组的中位数
140?
141 ? ? // 寻找每个组的中位数。首先对每组中的元素（至多为5个）进行插入排序，
142 ? ? // 然后从排序后的序列中选择出中位数。
143 ? ? int m=p;
144 ? ? for (int j=0,m=p;j
145 ? ? {
146 ? ? ? ? medians[j] = GetMedian(A,m,m+4);
147 ? ? ? ? m+=5;
148 ? ? }
149 ? ? medians[medianCount-1] = GetMedian(A,m,q);
150 ? ? //对第2步中找出的n/5（上取整）个中位数，递归调用SELECT以找出其中位数pivot。
151 ? ? //（如果是偶数去下中位数）
152 ? ? int pivot = WorseLinearSelect(medians,0,medianCount-1,(medianCount+1)/2);
153 ? ? //调用PARTITION过程，按照中位数pivot对输入数组进行划分。确定中位数pivot的位置r。
154 ? ? int r = partitionWithPivot(A,p,q,pivot);
155 ? ? int num = r-p+1;
156 ? ? //如果num=k，则返回pivot。否则，如果k
157 ? ? //若干k>num，则在高区找第(k-num)个最小元素。
158 ? ? if(num==k) return pivot;
159 ? ? else if (num>k) return WorseLinearSelect(A,p,r-1,k);
160 ? ? else return WorseLinearSelect(A,r+1,q,k-num);
161 }
162 #endif?
复制代码
?
?
main.cpp
?
?
复制代码
?1 #include
?2 #include
?3 #include
?4 using namespace std;
?5 #include "Select.h"
?6 #define ?N 10 ? //排序数组大小
?7 #define ?K 100 ? //排序数组范围0～K
?8 ////打印数组
?9 void print_element(vector A)
10 {
11 ? ? int len=A.size();
12 ? ? for (int i=0;i
13 ? ? {
14 ? ? ? ? std::cout<
15 ? ? }
16 ? ? std::cout<
17 }
18 int main()
19 {
20 ? ? Select s1;
21 ? ? int a[10]={23,4,34,345,3,21,45,246,98,50};
22 ? ? vector vec_int(a,a+10);
23 ? ? cout<<"原始数组"<
24 ? ? print_element(vec_int);
25 ? ? // 期望线性时间做选择测试
26 ? ? cout<<"期望线性时间做选择测试"<
27 ? ? for(int i=1;i<=N;i++)
28 ? ? {
29 ? ? ? ? int kMin=s1.RandomSelect(vec_int,0,N-1,i);