线性时间界的选择第k大元素的算法

本文主要参考《算法导论》第三版9.2 9.3节描述的线性时间界的选择第k大元素的算法
第一个算法期望运行时间为线性,这是一个广为人知的经典算法
利用快速排序的划分算法,选择枢轴进行划分,结束后如果枢轴是第n大元素且n=k则枢轴即为所求,如果n<k则递归地在n右边的子序列寻找k-n大的元素否则递归地在n左边的子序列寻找第k大元素直到找到所需元素
该算法的期望运行时间为线性,证明及伪代码请参考算法导论9.2节

第二个算法最坏运行时间为线性,假设算法在一个长为n的元素序列中寻找第i小的元素
以下是算法导论9,3节对该算法的描述:
1将输入的元素划分为[n/5]组，五个元素为一组，至多有一组由剩下的n mod 5个元素组成
2寻找这ceil(n/5)组中每一组的中位数:首先对每组元素插入排序，确定每组元素的中位数
3对第二部找出的ceil(n/5)组个中位数,递归调用找出其中位数x
4按x对输入序列进行划分,设划分结束后x是第k小的元素
5若i=k 返回x,若i<k则在x左侧子序列递归找出第i小元素否则在x 右侧子序列递归找出第i-k小的元素

该算法最坏运行时间为线性，证明见算法导论9.3节

以下实现用迭代形式实现第一个算法，用递归形式实现第二个算法,并且把第二个算法需要用到的插入排序改为其变体希尔排序

c++代码:

#include<iostream>#include<algorithm>#include<vector>#include<random>usingnamespacestd;template<typenameT>voidshellSort(vector<T>&value_seq,vector<size_t>&seq,size_t left,size_t right){size_t gap=seq.size();while(true){for(size_t i=0;i<gap;++i){for(size_t j=left+i+gap;j<=right;j+=gap){size_t temp=seq[j];size_t k=j-gap;for(;;k-=gap){if(value_seq[temp]<value_seq[seq[k]]){seq[k+gap]=seq[k];}else{seq[k+gap]=temp;break;}if(k<i+left+gap){seq[i+left]=temp;break;}}}}if(gap==1){break;}gap=gap/3+1;}}size_tdivide(vector<int>&value_seq,vector<size_t>&seq,size_t left,size_t right,size_t pivot){swap(seq[right],seq[pivot]);intp=seq[right];while(left<right){while(left<right&&value_seq[seq[left]]<=value_seq[p]){++left;}seq[right]=seq[left];while(left<right&&value_seq[seq[right]]>=value_seq[p]){--right;}seq[left]=seq[right];}seq[left]=p;returnleft;}size_tSelect(vector<int>&value_seq,vector<size_t>&seq,size_t left,size_t right,size_t rank){if(left==right){returnseq[left];}vector<size_t>mid_number_list((right-left+1)/5+1);vector<int>temp(mid_number_list.size());size_t i=left+4;for(;i<=right;i+=5){shellSort(value_seq,seq,i-4,i);mid_number_list[(i-left)/5]=(i-left)/5;temp[(i-left)/5]=value_seq[seq[i-2]];}size_t last_index;if(i-4<=right){shellSort(value_seq,seq,i-4,right);mid_number_list.back()=mid_number_list.size()-1;temp.back()=value_seq[seq[(right+i-4)/2]];last_index=(right+i-4)/2;}else{mid_number_list.pop_back();temp.pop_back();}size_t mid=Select(temp,mid_number_list,0,mid_number_list.size()-1,(mid_number_list.size()+1)/2);if(i-4>right||mid!=mid_number_list.size()-1){mid=mid*5+2+left;}else{mid=last_index;}mid=divide(value_seq,seq,left,right,mid);if(mid+1-left>rank){returnSelect(value_seq,seq,left,mid-1,rank);}elseif(mid+1-left<rank){returnSelect(value_seq,seq,mid+1,right,rank-mid-1+left);}else{returnseq[mid];}}size_tcommonDivide(vector<int>&value_seq,vector<size_t>&seq,size_t left,size_t right){intp=seq[right];while(left<right){while(left<right&&value_seq[seq[left]]<=value_seq[p]){++left;}seq[right]=seq[left];while(left<right&&value_seq[seq[right]]>=value_seq[p]){--right;}seq[left]=seq[right];}seq[left]=p;returnleft;}size_tcommonSelect(vector<int>&value_seq,vector<size_t>&seq,size_t left,size_t right,size_t rank){while(true){size_t divide_point=commonDivide(value_seq,seq,left,right);if(divide_point+1-left<rank){rank=rank-(divide_point+1)+left;left=divide_point+1;}elseif(divide_point+1-left>rank){right=divide_point-1;}else{returnseq[divide_point];}}}intmain(){constintN=123;vector<int>input(N);for(inti=0;i<N;++i){input[i]=i+1;}shuffle(input.begin(),input.end(),default_random_engine());cout<<"输入序列:";for(constauto&run:input){cout<<run<<" ";}cout<<endl;for(inti=1;i<=N;++i){vector<size_t>seq(N);for(size_t j=0;j<N;++j){seq[j]=j;}size_t index=Select(input,seq,0,seq.size()-1,i);cout<<"Select计算结果:"<<endl;cout<<"第"<<i<<"大的数:"<<input[index]<<" 位置:"<<index+1<<endl;for(size_t j=0;j<N;++j){seq[j]=j;}index=commonSelect(input,seq,0,seq.size()-1,i);cout<<"commonSelect计算结果:"<<endl;cout<<"第"<<i<<"大的数:"<<input[index]<<" 位置:"<<index+1<<endl;}return0;}