| « | August 2025 | » | | 日 | 一 | 二 | 三 | 四 | 五 | 六 | | | | | | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | | | | | | | |
|
| 公告 |
本站技术贴除标明为“原创”的之外，其余均为网上转载，文中我会尽量保留原作者姓名，若有侵权请与我联系，我将第一时间做出修改。谢谢！
——既瑜 |
| 统计 |
blog名称:★既瑜★
日志总数:183
评论数量:636
留言数量:-25
访问次数:1405652
建立时间:2005年3月12日 |
OICQ：215768265
njucs2001@hotmail.com
erichoo1982@gmail.com |
|
W3CHINA Blog首页 管理页面 写新日志 退出
 [【技术文档】]算法连载（2）--快速排序与插入排序的比较[转载] |
快速排序基本思想：选取A为某个元素，例如说t=A(s)，然后将其它的元素重新排列，使A(1:n)中的所有在t以前的元素都小于或等于t，而所有在t之后的元素都大于或等于t。
//语言：c++//目的：比较两个排序算法的时间复杂度//原代码：//Insertionsortint *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
//quicksortint 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 functionvoid 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; } }}
|
阅读全文(2597) | 回复(0) | 编辑 | 精华 |
|
