分治策略算法快速排序

快速排序法sort）是目前所公認(rèn)最快的排序方法之一（定），對(duì)左邊與右邊數(shù)列進(jìn)行排序，而影響快速排序法效率的正是軸心的選擇。///////////////////////////////////////////////////////////////////////////代碼1多數(shù)的教科書(shū)上所提及的版本(軸在最右側(cè))///////////////#include<iostream>#include<ctime>#include<iomanip>usingnamespacestd;#defineMAX10#defineSWAP(x,y){intt;t=x;x=y;y=t;}intpartition(int[],int,int);voidquicksort(int[],int,int);voidmain(){intnumber[MAX]=inti;srand(time(NULL));cout<<"排序前：";for(i=0;i<MAX;i++){number[i]=rand()%100;cout<<setw(6)<<number[i];}quicksort(number,0,MAX-1);cout<<"\n排序后：";for(i=0;i<MAX;cout<<setw(6)<<number[i];cout<<"\n";}intpartition(intnumber[],intleft,intright){inti,j,s;s=number[right];i=left-1;for(j=left;j<right;j++){if(number[j]<=s){i++;SWAP(number[i],number[j]);}}SWAP(number[i+1],number[right]);returni+1;}voidquicksort(intnumber[],intleft,intright){intq;if(left<right){ q=partition(number,left,quicksort(number,left,q-1);quicksort(number,q+1,right);}}/////////////////////////////////////代碼（軸在中心）/////////////////////////////////////////////#include<iostream>#include<ctime>#include<iomanip>usingnamespacestd;#defineMAX10#defineSWAP(x,y){intt;t=x;x=y;y=intpartition(int[],int,int);voidquicksort(int[],int,int);voidmain(){intnumber[MAX]={0};inti;srand(time(NULL));cout<<"排序前：";for(i=0;i<MAX;i++){number[i]=rand()%100;cout<<setw(6)<<number[i];}quicksort(number,0,MAX-1);cout<<"\n排序后：";for(i=0;i<MAX;i++)cout<<setw(6)<<number[i];cout<<"\n";}voidquicksort(intnumber[],intleft,intright){ inti,j,s;if(left<{ s=number[(left+right)/2];i=left-1;j=right+1;while(1){while(number[++i]<s);//向右找while(number[--j]>s);//向左找if(i>=j) break;SWAP(number[i],number[j]);}quicksort(number,left,i-1); //對(duì)左邊進(jìn)行遞quicksort(number,j+1,right); //對(duì)右邊進(jìn)行遞}}///////////////////////////////////////代碼（軸選在最左側(cè)///////////////////////////////////#include<iostream>#include<ctime>#include<iomanip>usingnamespacestd;#defineMAX10#defineSWAP(x,y){intt;t=x;x=y;y=intpartition(int[],int,int);voidquicksort(int[],int,int);voidmain(){intnumber[MAX]={0};inti;srand(time(NULL));cout<<"排序前：";for(i=0;i<MAX;i++){number[i]=rand()%100;cout<<setw(6)<<number[i];}quicksort(number,0,MAX-1);cout<<"\n排序后：";for(i=0;i<MAX;i++)cout<<setw(6)<<number[i];cout<<"\n";}intpartition(intnumber[],intleft,intright){ints;s=number[left];while(left<right){//while(number[right]>s)right--;while(number[left]<s)left++;SWAP(number[left],number[right]);}number[left]=s;//樞軸記錄到位returnleft;//返回樞軸位置}voidquicksort(intnum