快速排序基本思想:选取A为某个元素,例如说t=A(s),然后将其它的元素重新排列,使A(1:n)中的所有在t以前的元素都小于或等于t,而所有在t之后的元素都大于或等于t。 //语言:c++ //目的:比较两个排序算法的时间复杂度 //原代码: //Insertionsort int *Insertionsort(int *A,int n) { int j,item,i; for(j=2;j<=n;j++) { item=A[j]; i=j-1; while (item<A[i]) { A[i+1]=A[i]; i--; } A[i+1]=item; } return A; }//insertionsort //quicksort int Quickpass(int R[],int low,int high) { int down,up; //initialize flag down=low;up=high;R[0]=R[low]; //put benchmark record into R[0] while (down<up) { while((down<up)&&(R[up]>=R[0])) //scan from right to left up--; if(down<up) R[down++]=R[up]; while((down<up)&&(R[down]<=R[0]))//scan from left to right down++; if(down<up) R[up--]=R[down]; } R[down]=R[0]; return down; }//one time of sortion int *Quicksort(int R[],int low,int high) { int mid; if (low<high) { mid=Quickpass(R,low,high); Quicksort(R,low,mid-1); Quicksort(R,mid+1,high); } return R;
}//quicksort #include<iostream.h> #include<time.h> #include<stdlib.h> //////main function void main() { clock_t start,end; float elapsed1; //time of quicksort float elapsed2; //time of insertionsort const int n=30001; const int m=30000; int i;int w; cout<<"|------快速排序与插入排序算法比较-----|"<<endl; cout<<"|-----------数据规模:30000-----------|"<<endl; cout<<"|---power by zhanjiantao(028054115)---|"<<endl; cout<<"---------------------------------------"<<endl; cout<<"running……"<<endl; while(w) { //INSERTIONSORT start=clock(); //start time int A[m]; for(i=0;i<m;i++) A[i]=rand(); Insertionsort(A,m);
end=clock(); //finish time elapsed2=((float)end-start)/CLOCKS_PER_SEC; //INSERTIONSORT
//QUICKSORT start=clock();//start time int R[n]; for(i=1;i<=n;i++) R[i]=rand();
Quicksort(R,1,n); end=clock(); //time finish elapsed1=((float)end-start)/CLOCKS_PER_SEC; //QUICKSORT cout<<"选择<3>验证insertionsort的正确性"<<endl; cout<<"选择<2>验证quicksort的正确性"<<endl; cout<<"选择<1>比较算法运算时间"<<endl; cout<<"选择<0>退出"<<endl; cin>>w; switch(w){ case 3:for(i=0;i<m;i++) cout<<A[i]<<" "; break; case 2:for(i=1;i<n;i++) cout<<A[i]<<" "; break; case 1: cout<<"insertionsort的运行时间:"<<elapsed2<<"s"<<endl; cout<<"quicksort的运行时间:"<<elapsed1<<"s"<<endl; break; case 0: break; default: cout<<"错误!请输入正确的功能序号!"<<endl; } } } 
|