本文主要参考《算法导论》第三版9.2 9.3节描述的线性时间界的选择第k大元素的算法第一个算法期望运行时间为线性,这是一个广为人知的经典算法利用快速排序的划分算法,选择枢轴进行划分,结束后如果枢轴是第n大元素且nk则枢轴即为所求,如果nk则递归地在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)组个中位数,递归调用找出其中位数x4按x对输入序列进行划分,设划分结束后x是第k小的元素5若ik 返回x,若ik则在x左侧子序列递归找出第i小元素否则在x 右侧子序列递归找出第i-k小的元素该算法最坏运行时间为线性证明见算法导论9.3节以下实现用迭代形式实现第一个算法用递归形式实现第二个算法,并且把第二个算法需要用到的插入排序改为其变体希尔排序c代码:#includeiostream#includealgorithm#includevector#includerandomusingnamespacestd;templatetypenameTvoidshellSort(vectorTvalue_seq,vectorsize_tseq,size_t left,size_t right){size_t gapseq.size();while(true){for(size_t i0;igap;i){for(size_t jleftigap;jright;jgap){size_t tempseq[j];size_t kj-gap;for(;;k-gap){if(value_seq[temp]value_seq[seq[k]]){seq[kgap]seq[k];}else{seq[kgap]temp;break;}if(kileftgap){seq[ileft]temp;break;}}}}if(gap1){break;}gapgap/31;}}size_tdivide(vectorintvalue_seq,vectorsize_tseq,size_t left,size_t right,size_t pivot){swap(seq[right],seq[pivot]);intpseq[right];while(leftright){while(leftrightvalue_seq[seq[left]]value_seq[p]){left;}seq[right]seq[left];while(leftrightvalue_seq[seq[right]]value_seq[p]){--right;}seq[left]seq[right];}seq[left]p;returnleft;}size_tSelect(vectorintvalue_seq,vectorsize_tseq,size_t left,size_t right,size_t rank){if(leftright){returnseq[left];}vectorsize_tmid_number_list((right-left1)/51);vectorinttemp(mid_number_list.size());size_t ileft4;for(;iright;i5){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-4right){shellSort(value_seq,seq,i-4,right);mid_number_list.back()mid_number_list.size()-1;temp.back()value_seq[seq[(righti-4)/2]];last_index(righti-4)/2;}else{mid_number_list.pop_back();temp.pop_back();}size_t midSelect(temp,mid_number_list,0,mid_number_list.size()-1,(mid_number_list.size()1)/2);if(i-4right||mid!mid_number_list.size()-1){midmid*52left;}else{midlast_index;}middivide(value_seq,seq,left,right,mid);if(mid1-leftrank){returnSelect(value_seq,seq,left,mid-1,rank);}elseif(mid1-leftrank){returnSelect(value_seq,seq,mid1,right,rank-mid-1left);}else{returnseq[mid];}}size_tcommonDivide(vectorintvalue_seq,vectorsize_tseq,size_t left,size_t right){intpseq[right];while(leftright){while(leftrightvalue_seq[seq[left]]value_seq[p]){left;}seq[right]seq[left];while(leftrightvalue_seq[seq[right]]value_seq[p]){--right;}seq[left]seq[right];}seq[left]p;returnleft;}size_tcommonSelect(vectorintvalue_seq,vectorsize_tseq,size_t left,size_t right,size_t rank){while(true){size_t divide_pointcommonDivide(value_seq,seq,left,right);if(divide_point1-leftrank){rankrank-(divide_point1)left;leftdivide_point1;}elseif(divide_point1-leftrank){rightdivide_point-1;}else{returnseq[divide_point];}}}intmain(){constintN123;vectorintinput(N);for(inti0;iN;i){input[i]i1;}shuffle(input.begin(),input.end(),default_random_engine());cout输入序列:;for(constautorun:input){coutrun ;}coutendl;for(inti1;iN;i){vectorsize_tseq(N);for(size_t j0;jN;j){seq[j]j;}size_t indexSelect(input,seq,0,seq.size()-1,i);coutSelect计算结果:endl;cout第i大的数:input[index] 位置:index1endl;for(size_t j0;jN;j){seq[j]j;}indexcommonSelect(input,seq,0,seq.size()-1,i);coutcommonSelect计算结果:endl;cout第i大的数:input[index] 位置:index1endl;}return0;}
线性时间界的选择第k大元素的算法
本文主要参考《算法导论》第三版9.2 9.3节描述的线性时间界的选择第k大元素的算法第一个算法期望运行时间为线性,这是一个广为人知的经典算法利用快速排序的划分算法,选择枢轴进行划分,结束后如果枢轴是第n大元素且nk则枢轴即为所求,如果nk则递归地在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)组个中位数,递归调用找出其中位数x4按x对输入序列进行划分,设划分结束后x是第k小的元素5若ik 返回x,若ik则在x左侧子序列递归找出第i小元素否则在x 右侧子序列递归找出第i-k小的元素该算法最坏运行时间为线性证明见算法导论9.3节以下实现用迭代形式实现第一个算法用递归形式实现第二个算法,并且把第二个算法需要用到的插入排序改为其变体希尔排序c代码:#includeiostream#includealgorithm#includevector#includerandomusingnamespacestd;templatetypenameTvoidshellSort(vectorTvalue_seq,vectorsize_tseq,size_t left,size_t right){size_t gapseq.size();while(true){for(size_t i0;igap;i){for(size_t jleftigap;jright;jgap){size_t tempseq[j];size_t kj-gap;for(;;k-gap){if(value_seq[temp]value_seq[seq[k]]){seq[kgap]seq[k];}else{seq[kgap]temp;break;}if(kileftgap){seq[ileft]temp;break;}}}}if(gap1){break;}gapgap/31;}}size_tdivide(vectorintvalue_seq,vectorsize_tseq,size_t left,size_t right,size_t pivot){swap(seq[right],seq[pivot]);intpseq[right];while(leftright){while(leftrightvalue_seq[seq[left]]value_seq[p]){left;}seq[right]seq[left];while(leftrightvalue_seq[seq[right]]value_seq[p]){--right;}seq[left]seq[right];}seq[left]p;returnleft;}size_tSelect(vectorintvalue_seq,vectorsize_tseq,size_t left,size_t right,size_t rank){if(leftright){returnseq[left];}vectorsize_tmid_number_list((right-left1)/51);vectorinttemp(mid_number_list.size());size_t ileft4;for(;iright;i5){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-4right){shellSort(value_seq,seq,i-4,right);mid_number_list.back()mid_number_list.size()-1;temp.back()value_seq[seq[(righti-4)/2]];last_index(righti-4)/2;}else{mid_number_list.pop_back();temp.pop_back();}size_t midSelect(temp,mid_number_list,0,mid_number_list.size()-1,(mid_number_list.size()1)/2);if(i-4right||mid!mid_number_list.size()-1){midmid*52left;}else{midlast_index;}middivide(value_seq,seq,left,right,mid);if(mid1-leftrank){returnSelect(value_seq,seq,left,mid-1,rank);}elseif(mid1-leftrank){returnSelect(value_seq,seq,mid1,right,rank-mid-1left);}else{returnseq[mid];}}size_tcommonDivide(vectorintvalue_seq,vectorsize_tseq,size_t left,size_t right){intpseq[right];while(leftright){while(leftrightvalue_seq[seq[left]]value_seq[p]){left;}seq[right]seq[left];while(leftrightvalue_seq[seq[right]]value_seq[p]){--right;}seq[left]seq[right];}seq[left]p;returnleft;}size_tcommonSelect(vectorintvalue_seq,vectorsize_tseq,size_t left,size_t right,size_t rank){while(true){size_t divide_pointcommonDivide(value_seq,seq,left,right);if(divide_point1-leftrank){rankrank-(divide_point1)left;leftdivide_point1;}elseif(divide_point1-leftrank){rightdivide_point-1;}else{returnseq[divide_point];}}}intmain(){constintN123;vectorintinput(N);for(inti0;iN;i){input[i]i1;}shuffle(input.begin(),input.end(),default_random_engine());cout输入序列:;for(constautorun:input){coutrun ;}coutendl;for(inti1;iN;i){vectorsize_tseq(N);for(size_t j0;jN;j){seq[j]j;}size_t indexSelect(input,seq,0,seq.size()-1,i);coutSelect计算结果:endl;cout第i大的数:input[index] 位置:index1endl;for(size_t j0;jN;j){seq[j]j;}indexcommonSelect(input,seq,0,seq.size()-1,i);coutcommonSelect计算结果:endl;cout第i大的数:input[index] 位置:index1endl;}return0;}
