算法导论-顺序统计(二)
lect(vector &A,int p,int q,int k)
?2 {
?3 ? ? // 将输入数组的n个元素划分为n/5（上取整）组，每组5个元素，
?4 ? ? // 且至多只有一个组有剩下的n%5个元素组成。
?5 ? ? if (p==q) return A[p];
?6?
?7 ? ? int len=q-p+1;
?8 ? ? int medianCount=1;
?9 ? ? if (len>5)
10 ? ? ? ? medianCount = len%5 >0 ? len/5 + 1 : len/5;
11 ? ? vector medians(medianCount);//存放每组的中位数
12?
13 ? ? // 寻找每个组的中位数。首先对每组中的元素（至多为5个）进行插入排序，
14 ? ? // 然后从排序后的序列中选择出中位数。
15 ? ? int m=p;
16 ? ? for (int j=0,m=p;j
17 ? ? {
18 ? ? ? ? medians[j] = GetMedian(A,m,m+4);
19 ? ? ? ? m+=5;
20 ? ? }
21 ? ? medians[medianCount-1] = GetMedian(A,m,q);
22 ? ? //对第2步中找出的n/5（上取整）个中位数，递归调用SELECT以找出其中位数pivot。
23 ? ? //（如果是偶数去下中位数）
24 ? ? int pivot = WorseLinearSelect(medians,0,medianCount-1,(medianCount+1)/2);
25 ? ? //调用PARTITION过程，按照中位数pivot对输入数组进行划分。确定中位数pivot的位置r。
26 ? ? int r = partitionWithPivot(A,p,q,pivot);
27 ? ? int num = r-p+1;
28 ? ? //如果num=k，则返回pivot。否则，如果k
29 ? ? //若干k>num，则在高区找第(k-num)个最小元素。
30 ? ? if(num==k) return pivot;
31 ? ? else if (num>k) return WorseLinearSelect(A,p,r-1,k);
32 ? ? else return WorseLinearSelect(A,r+1,q,k-num);
33 }
复制代码
?
?
?
?
?
?
该算法在最坏情况下运行时间为Θ(n)
代码实现(c++)：
? 1 template//插入排序
? 2 void insertion_sort(vector &A,int p,int q)
? 3 {
? 4 ? ? int i,j;
? 5 ? ? T key;
? 6 ? ? int len=q-p+1;
? 7 ? ? for (j=p+1;j<=q;j++)
? 8 ? ? {
? 9 ? ? ? ? i=j-1;
?10 ? ? ? ? key=A[j];
?11 ? ? ? ? while (i>=p&&A[i]>key)
?12 ? ? ? ? {
?13 ? ? ? ? ? ? A[i+1]=A[i];
?14 ? ? ? ? ? ? i--;
?15 ? ? ? ? }
?16 ? ? ? ? A[i+1]=key;
?17 ? ? }
?18 }
?19 /*
?20 ?* ? ?利用插入排序选择中位数
?21 ?*/
?22 template
?23 T GetMedian(vector &A,int p,int q)
?24 {
?25 ? ? insertion_sort(A,p,q);//插入排序
?26 ? ? return A[(q-p)/2 + p];//返回中位数,有两个中位数的话返回较小的那个
?27 }
?28 /*
?29 ?* ? ?根据指定的划分主元pivot来划分数组
?30 ?* ? ?并返回主元的顺序位置
?31 ?*/
?32 template
?33 int ?partitionWithPivot(vector &A,int p,int q,T piovt)
?34 {
?35 ? ? //先把主元交换到数组首元素
?36 ? ? for (int i=p;i
?37 ? ? {
?38 ? ? ? ? if (A[i] == piovt)
?39 ? ? ? ? {
?40 ? ? ? ? ? ? Swap(A[i],A[p]);
?41 ? ? ? ? ? ? break;
?42 ? ? ? ? }
?43 ? ? }
?44 ? ? //常规的快速排序划分程序
?45 ? ? //
?46 ? ? T x=A[p];
?47 ? ? int i=p;
?48 ? ? for (int j=p+1;j<=q;j++)
?49 ? ? {
?50 ? ? ? ? if (A[j]
?51 ? ? ? ? {
?52 ? ? ? ? ? ? i=i+1;
?53 ? ? ? ? ? ? Swap(A[i],A[j]);
?54 ? ? ? ? }
?55 ? ? }
?56 ? ? Swap(A[p],A[i]);
?57 ? ? return i;
?58 }
?59 /*
?60 ?* ? ?最坏情况下线性时间选择算法
?61 ?* ? ?此算法依然是建立在快速排序的划分算法基础之上的
?62 ?* ? ?但是与randomizedSelect算法的不同指之处，就是次算法的本质
?63 ?* ? ?是保证了每次划分选择的划分主元一定是一个较好的主元，算法先对数组5个一组进行分组
?64 ?* ? ?然后选择每组的中位数，再递归的选择各组中位数中的中位数作为数组的划分主元，以此保证划分的平衡性
?65 ?* ? ?选择中位数的时候必须使用递归调用的方法才能降低时间复杂度
?66 ?* ? ?从而保证在最坏情况下都得到一个好的划分
?67 ?* ? ?最坏情况下时间复杂度为O(n)
?68 ?*/
?69 template
?70 T WorseLinearSelect(vector &A,int p,int q,int k)
?71 {
?72 ? ? // 将输入数组的n个元素划分为n/5（上取整）组，每组5个元素，
?73 ? ? // 且至多只有一个组有剩下的n%5个元素组成。
?74 ? ? if (p==q) return A[p];
?75?
?76 ? ? int len=q-p+1;
?77 ? ? int medianCount=1;
?78 ? ? if (len>5)
?79 ? ? ? ? medianCount = len%5 >0 ? len/5 + 1 : len/5;
?80 ? ? vector medians(medianCount);//存放每组的中位数
?81?
?82 ? ? // 寻找每个组的中位数。首先对每组中的元素（至多为5个）进行插入排序，
?83 ? ? // 然后从排序后的序列中选择出中位数。
?84 ? ? int m=p;