算法设计与分析实验2——线性时间选择算法

第2次上机实验的内容：在快速排序算法基础上，进一步完成线性时间选择算法，并且用不同数据量进行实验对比分析，要求分析算法的时间复杂性并且形成分析报告；#includectime#includeiostream#includecstdlibusingnamespacestd;#defineLENGTH1000#defineRANGE1000voidexchange(int&i,int&j){intn;n=i;i=j;j=n;}intpartition(inta[],intp,intr,intx){inti,j;i=p-1;for(j=p;j=r-1;j++){if(a[j]=x){i++;exchange(a[i],a[j]);}}exchange(a[i+1],a[r]);return(i+1);}voidquicksort(inta[],intp,intr){intm;if(pr){m=partition(a,p,r,a[r]);quicksort(a,p,m-1);quicksort(a,m+1,r);}}intSelect(inta[],intp,intr,intk){inti,j,x;if(r-p75){quicksort(a,p,r);return(a[p+k-1]);}for(i=0;i=(r-p-4)/5;i++){quicksort(a,p+5*i,p+5*i+4);exchange(a[p+i],a[p+5*i+2]);}x=Select(a,p,p+(r-p-4)/5,(r-p-4)/10);i=partition(a,p,r,x);j=i-p+1;if(k=j)return(Select(a,p,i,k));elsereturn(Select(a,i+1,r,k-j));}intmain(){inta[LENGTH];inti,k,x;srand((unsigned)time(NULL));for(i=0;iLENGTH;i++){a[i]=rand()%(RANGE+1);printf(%5d,a[i]);}clock_tstart,end;printf(\n输入要查找第几小的元素\n);scanf(%d,&k);start=clock();x=Select(a,0,LENGTH-1,k);end=clock();printf(第%d小的元素为:%d\n,k,x);coutProcessingTime:end-startendl;return1;}