快速排序基本思想：选取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;
}
}
}
