0006算法笔记-【分治法】线性时间选择

线性时间选择问题：给定线性序集中n个元素和一个整数k,1<k<n要求找出这n个元素中第k小的元素，（这里给定的线性集是无序的）。1、随机划分线性选择线性时间选择随机划分法可以模仿随机化快速排序算法设计。基本思想是对输入数组进行递归划分，与快速排序不同的是，它只对划分出的子数组之一进行递归处理程序清单如下：1.2.3.1.2.3.4.5.6.//2d9-1随机划分线性时间选择#include"stdafx.h"#include<iostream>#include<ctime>usingnamespacestd;7-inta[]={5,7,3,4,8,6,9,1,2};&template<classType〉voidSwap(Type&x,Type&y);11.12-inlineintRandom(intx,inty);13.template<classType>intPartition(Typea[],intp,intr);16.template<classType>intRandomizedPartition(Typea[],intp,intr);19.template<classType>21-TypeRandomizedSelect(Typea[],intp,intr,intk);22.23-intmain(){for(inti=0;i<9;i++){{26.27.28.29.30.31.32.33.34.35.36.37.38.39.40.41.42.43.44.45.46.47.48.49.50.51.52.53.54.55.56.57.58.59.60.61.62.63.64.65.66.67.68.69.cout<<a[i]<<}cout<<endl;cout<<RandomizedSelect(a,0,8,3)<<endl;}template<classType〉voidSwap(Type&x,Type&y){Typetemp=x;x=y;y=temp;}inlineintRandom(intx,inty){srand((unsigned)time(0));intran_num=rand()%(y-x)+x;returnran_num;}template<classType〉intPartition(Typea[],intp,intr){inti=p,j=r+1;Typex=a[p];while(true){while(a[++i]<x&&i<r);while(a[--j]>x);if(i>=j){break;}Swap(a[i],a[j]);}a[p]=a[j];a[j]=x;returnj;}template<classType>70.71.72.70.71.72.73.74.75.76.77.78.79.80.81.82.83.84.85.86.87.88.89.90.91.92.93.94.95.}intRandomizedPartition(Typea[],intp,intr){inti=Random(p,r);Swap(a[i],a[p]);returnPartition(a,p,r);}template<classType〉TypeRandomizedSelect(Typea[],intp,intr,intk){if(p==r){returna[p];}inti=RandomizedPartition(a,p,r);intj=i-p+1;if(k<=j){returnRandomizedSelect(a,p,i,k);}else{//由于已知道子数组a[p:i]中的元素均小于要找的第k小元素//因此，要找的a[p:r]中第k小元素是a[i+1:r]中第k-j小元素。returnRandomizedSelect(a,i+1,r,k-j);}程序解释：利用随机函数产生划分基准，将数组a[p:r]划分成两个子数组a[p:i]和a[i+1:r]，使a[p:i冲的每个元素都不大于a[i+1:r冲的每个元素。接着"j=i-p+1"计算a[p:i]中元素个数j•如果k<=j,则a[p:r冲第k小元素在子数组a[p:i]中，如果k>j，则第k小元素在子数组a[i+1:r]中。注意：由于已知道子数组a[p:i冲的元素均小于要找的第k小元素,因此，要找的a[p:r]中第k小元素是a[i+1:r]中第k-j小元素。在最坏的情况下，例如：总是找到最小元素时，总是在最大元素处划分，这是时间复杂度为O(n"2)。但平均时间复杂度与n呈线性关

系，为0(n)(数学证明过程略过，可参考王云鹏论文《线性时间选择算法时间复杂度深入研究》)。2、利用中位数线性时间选择中位数：是指将数据按大小顺序排列起来，形成一个数列，居于数列中间位置的那个数据。算法思路：如果能在线性时间内找到一个划分基准使得按这个基准所划分出的2个子数组的长度都至少为原数组长度的E倍(0<£<1)，那么就可以在最坏情况下用0(n)时间完成选择任务。例如，当£=9/10,算法递归调用所产生的子数组的长度至少缩短1/10。所以，在最坏情况下，算法所需的计算时间T(n)满足递推式T(n)<=T(9n/10)+O(n)。由此可得T(n)=O(n)o实现步骤：将所有的数n个以每5个划分为一组共「门组，将不足5个的那组忽略，然后用任意一种排序算法，因为只对5个数进行排序，所以任取一种排序法就可以了。将每组中的元素排好序再分别取每组的中位数，得到门5I个中位数。取这门三|个中位数的中位数，如果|是偶数，就找它的2个中位数中较大的一个作为划分基准。6.6.将全部的数划分为两个部分，小于基准的在左边，大于等于基准的放右边。在这种情况下找出的基准x至少比.J［个元素大。因为在每一组中有2个元素小于本组的中位数，有屮巧-屮(1/2)吆珂计5-i」个小于基准，中位数处于l./2*Ln/5-l_［，即「n/5］个中位数中又有2'i\个小于基准X。因此至少有也/5-1」+附-5)/m」h(W-5_plO)个元素小于基准X。同理基准X也至少比.|个元素小。而当n>75时.小.—|>n/4所以按此基准划分所得的2个子数组的长度都至少缩短1/4。程序清单如下:[cpp][cpp]viewplaincopy1.//2d9-2中位数线性时间选择2.#include"stdafx.h"3.#include<ctime>4.#include<iostream>5.usingnamespacestd;7.&9.10.11.12.13.14.15.16.17.18.19.20.21.22.23.24.25.26.27.28.29.30.31.32.33.34.35.36.37.38.39.40.41.42.43.44.45.46.47.48.49.50.template<classType〉voidSwap(Type&x,Type&y);inlineintRandom(intx,inty);template<classType〉voidBubbleSort(Typea[],intp,intr);template<classType>intPartition(Typea[],intp,intr,Typex);template<classType>TypeSelect(Typea[],intp,intr,intk);intmain(){//初始化数组inta[100];//必须放在循环体外面srand((unsigned)time(0));for(inti=0;i<100;i++){a[i]=Random(0,500);cout<<”a[”<<i<<”]:”<<a[i]<<””；}cout<<endl;cout<<"第83小元素是"<<Select(a,0,99,83)<<endl;〃重新排序，对比结果BubbleSort(a,0,99);for(inti=0;i<100;i++){cout<<"a["<<i<<"]:"<<a[i]<<}cout<<endl;}template<classType>voidSwap(Type&x,Type&y){

51.52.53.54.55.56.57.58.59.60.61.62.63.64.65.66.67.68.69.70.71.72.73.74.75.76.77.78.79.80.81.82.83.84.85.86.87.88.89.90.91.92.93.94.Typetemp=x;x=y;y=temp;}inlineintRandom(intx,inty){intran_num=rand()%(y-x)+x;returnran_num;}//冒泡排序template<classType〉voidBubbleSort(Typea[],intp,intr){//记录一次遍历中是否有元素的交换boolexchange;for(inti=p;i<=r-1;i++){exchange=false;for(intj=i+1;j<=r;j++){if(a[j]<a[j-1]){Swap(a[j],a[j-1]);exchange=true;}}〃如果这次遍历没有元素的交换，那么排序结束if(false==exchange){break;}}}template<classType〉intPartition(Typea[],intp,intr,Typex){inti=p-1,j=r+1;while(true){while(a[++i]<x&&i<r);

while(a[--j]>x);if(i>=j){break;}Swap(a[i],a[j]);}returnj;}template<classType〉TypeSelect(Typea[],intp,intr,intk){if(r-p<75){BubbleSort(a,p,r);returna[p+k-1];}//(r-p-4)/5相当于n-5for(inti=0;i<=(r-p-4)/5;i++){//将元素每5个分成一组，分别排序，并将该组中位数与a[p+i]交换位置//使所有中位数都排列在数组最左侧，以便进一步查找中位数的中位数BubbleSort(a,p+5*i,p+5*i+4);Swap(a[p+5*i+2],a[p+i]);}//找中位数的中位数Typex=Select(a,p,p+(r-p-4)/5,(r-p-4)/10);inti=Partition(a,p,r,x);intj=i-p+1;if(k<=j){returnSelect(a,p,i,k);}else{returnSelect(a,i+1,r,k-j);}}95.96.97.98.99.100.101.102.103.104.105.106.107.108.109.110.111.112.113.114.115.116.117.118.119.120.121.122.123.124.125.126.127.128.129.130.131.132.133.134.运行结果如下:I_I_HIC:\V/!ndows\system32\cmd.exe[D|回|・^i|•51:427a[26]：224a[27]：40a[28]：246aE2?]：172aE30J：26aE31]：469a[32J：la[33J：2HIa[34]：26a[35]：91&[361:169a[3?J：376aE38J：459aE3?]：309aE40J：398a[41J：71a[421:457a[43]：426&[441:153a[45J：475&[461:44VaE47J：499aE48J：76a[49J：240a[501:449a[51]：378&[521:253&[531:222aE54J：l&3aE55J：114aE56J：186a[57J：171a[581:76a[591：441a[60]：299&[611:255&[621:435aEG3J：177aE64J：472a[65J：36a[66J：258a[67]：406&[68X229a[69]：3G?aE70J：laE71J：274aE72J：388aE73J：290a[74J：83a[75]：422a[76]：62a[77]：56a[78J：465aE79J：l?7aE80J：492aE81J：118a[821：195a[83]：362&[841:151a[85]：24&[861:52aE87J：51a[881：494aE89J：327a[?0J：17a[?l]：339a[92]：387a[93]：416a[94]：lG?aE?5J：431aE96J：108aE97J：289a[98J：53a[99J：193第83小元素是422a[0]：17atl]：2a[2]：la[3]：4a[4J：la[5J：24aE6J：26aE7J：26aE8J：36a[93：40a[101:51atll]：52a[12]：53a[13]：56aE14J：G0aE15J：G2aL16J：52a[17J：71a[181：76all9]：76a[20]：83a[21J：91151173195240290365388426457499a[28J：153a[36J：175a[44J：197a[52J：246a[60J：299a[68J：367aC76J：398a[84J：427a[92J：459a[29J