分享
 
 
 

算法连载(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;

}

}

}

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
2023年上半年GDP全球前十五强
 百态   2023-10-24
美众议院议长启动对拜登的弹劾调查
 百态   2023-09-13
上海、济南、武汉等多地出现不明坠落物
 探索   2023-09-06
印度或要将国名改为“巴拉特”
 百态   2023-09-06
男子为女友送行,买票不登机被捕
 百态   2023-08-20
手机地震预警功能怎么开?
 干货   2023-08-06
女子4年卖2套房花700多万做美容:不但没变美脸,面部还出现变形
 百态   2023-08-04
住户一楼被水淹 还冲来8头猪
 百态   2023-07-31
女子体内爬出大量瓜子状活虫
 百态   2023-07-25
地球连续35年收到神秘规律性信号,网友:不要回答!
 探索   2023-07-21
全球镓价格本周大涨27%
 探索   2023-07-09
钱都流向了那些不缺钱的人,苦都留给了能吃苦的人
 探索   2023-07-02
倩女手游刀客魅者强控制(强混乱强眩晕强睡眠)和对应控制抗性的关系
 百态   2020-08-20
美国5月9日最新疫情:美国确诊人数突破131万
 百态   2020-05-09
荷兰政府宣布将集体辞职
 干货   2020-04-30
倩女幽魂手游师徒任务情义春秋猜成语答案逍遥观:鹏程万里
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案神机营:射石饮羽
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案昆仑山:拔刀相助
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案天工阁:鬼斧神工
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案丝路古道:单枪匹马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:与虎谋皮
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:李代桃僵
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:指鹿为马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:小鸟依人
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:千金买邻
 干货   2019-11-12
 
推荐阅读
 
 
 
>>返回首頁<<
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有