算法连载(2)--快速排序与插入排序的比较

王朝other·作者佚名  2006-01-09
窄屏简体版  字體: |||超大  

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

}

}

}

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
 
 
© 2005- 王朝網路 版權所有 導航