算法导论-顺序统计(三)
pivot。
?92 ? ? //（如果是偶数去下中位数）
?93 ? ? int pivot = WorseLinearSelect(medians,0,medianCount-1,(medianCount+1)/2);
?94 ? ? //调用PARTITION过程，按照中位数pivot对输入数组进行划分。确定中位数pivot的位置r。
?95 ? ? int r = partitionWithPivot(A,p,q,pivot);
?96 ? ? int num = r-p+1;
?97 ? ? //如果num=k，则返回pivot。否则，如果k
?98 ? ? //若干k>num，则在高区找第(k-num)个最小元素。
?99 ? ? if(num==k) return pivot;
100 ? ? else if (num>k) return WorseLinearSelect(A,p,r-1,k);
101 ? ? else return WorseLinearSelect(A,r+1,q,k-num);
102 }
复制代码
4、完整测试代码（c++） ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
Select.h
?
?
复制代码
? 1 #ifndef SELECT_HH
? 2 #define SELECT_HH
? 3 template
? 4 class Select
? 5 {
? 6 public:
? 7 ? ? T RandomSelect(vector &A,int p,int q,int k);//期望线性时间做选择
? 8 ? ? T WorseLinearSelect(vector &A,int p,int q,int k);//最坏情况线性时间的选择
? 9 private:
?10 ? ? void Swap(T &m,T &n);//交换数据
?11 ? ? int Random_Partition(vector &A,int p,int q);//随机快排分划
?12 ? ? void insertion_sort(vector &A,int p,int q);//插入排序
?13 ? ? T GetMedian(vector &A,int p,int q);
?14 ? ? int partitionWithPivot(vector &A,int p,int q,T piovt);//根据指定主元pivot来划分数据并返回主元的顺序位置
?15 };
?16?
?17 template//交换数据
?18 void Select::Swap(T &m,T &n)
?19 {
?20 ? ? T tmp;
?21 ? ? tmp=m;
?22 ? ? m=n;
?23 ? ? n=tmp;
?24 }
?25?
?26 /***********随机快速排序分划程序*************/
?27 template
?28 int Select::Random_Partition(vector &A,int p,int q)
?29 {
?30 ? ? //随机选择主元，与第一个元素交换
?31 ? ? srand(time(NULL));
?32 ? ? int m=rand()%(q-p+1)+p;
?33 ? ? Swap(A[m],A[p]);
?34 ? ? //下面与常规快排划分一样
?35 ? ? T x=A[p];
?36 ? ? int i=p;
?37 ? ? for (int j=p+1;j<=q;j++)
?38 ? ? {
?39 ? ? ? ? if (A[j]
?40 ? ? ? ? {
?41 ? ? ? ? ? ? i=i+1;
?42 ? ? ? ? ? ? Swap(A[i],A[j]);
?43 ? ? ? ? }
?44 ? ? }
?45 ? ? Swap(A[p],A[i]);
?46 ? ? return i;
?47 }
?48 /***********随机选择统计函数*************/
?49 template
?50 T Select::RandomSelect(vector &A,int p,int q,int k)//随机选择统计，以期望线性时间做选择
?51 {
?52 ? ? if (p==q) return A[p];
?53 ? ? int pivot=Random_Partition(A,p,q);//随机选择主元，把数组进行划分为两部分
?54 ? ? int i=pivot-p+1;
?55 ? ? if (i==k )return A[pivot];
?56 ? ? else if (i
?57 ? ? else return RandomSelect(A,p,pivot-1,k);//第k小的数不在主元右边，则在左边递归选择
?58 }
?59?
?60 template//插入排序
?61 void Select::insertion_sort(vector &A,int p,int q)
?62 {
?63 ? ? int i,j;
?64 ? ? T key;
?65 ? ? int len=q-p+1;
?66 ? ? for (j=p+1;j<=q;j++)
?67 ? ? {
?68 ? ? ? ? i=j-1;
?69 ? ? ? ? key=A[j];
?70 ? ? ? ? while (i>=p&&A[i]>key)
?71 ? ? ? ? {
?72 ? ? ? ? ? ? A[i+1]=A[i];
?73 ? ? ? ? ? ? i--;
?74 ? ? ? ? }
?75 ? ? ? ? A[i+1]=key;
?76 ? ? }
?77 }
?78 /*
?79 ?* ? ?利用插入排序选择中位数
?80 ?*/
?81 template
?82 T Select::GetMedian(vector &A,int p,int q)
?83 {
?84 ? ? insertion_sort(A,p,q);//插入排序
?85 ? ? return A[(q-p)/2 + p];//返回中位数,有两个中位数的话返回较小的那个
?86 }
?87 /*
?88 ?* ? ?根据指定的划分主元pivot来划分数组
?89 ?* ? ?并返回主元的顺序位置
?90 ?*/
?91 template
?92 int ?Select::partitionWithPivot(vector &A,int p,int q,T piovt)
?93 {
?94 ? ? //先把主元交换到数组首元素
?95 ? ? for (int i=p;i
?96 ? ? {
?97 ? ? ? ? if (A[i] == piovt)
?98 ? ? ? ? {
?99 ? ? ? ? ? ? Swap(A[i],A[p]);
100 ? ? ? ? ? ? break;
101 ? ? ? ? }
102 ? ? }
103 ? ? //常规的快速排序划分程序
104 ? ? //
105 ? ? T x=A[p];
106 ? ? int i=p;
107 ? ? for (int j=p+1;j<=q;j++)
108 ? ? {