算法连载（2）--快速排序与插入排序的比较 - Compower Studio - CSD...

来源：百度文库 编辑：神马文学网 时间：2024/04/18 09:10:45
算法连载（2）--快速排序与插入排序的比较快速排序基本思想：选取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+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{
while((down=R[0])) //scan from right to left
up--;
if(downR[down++]=R[up];
while((downdown++;
if(downR[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{
mid=Quickpass(R,low,high);
Quicksort(R,low,mid-1);
Quicksort(R,mid+1,high);
}
return R;}//quicksort#include
#include
#include
//////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<<"|------快速排序与插入排序算法比较-----|"<cout<<"|-----------数据规模：30000-----------|"<cout<<"|---power by zhanjiantao(028054115)---|"<cout<<"---------------------------------------"<cout<<"running……"<{
//INSERTIONSORT
start=clock(); //start time
int A[m];
for(i=0;iA[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的正确性"<cout<<"选择<2>验证quicksort的正确性"<cout<<"选择<1>比较算法运算时间"<cout<<"选择<0>退出"<cin>>w;
switch(w){  case 3:for(i=0;icout<break;
case 2:for(i=1;icout<break;
case 1: cout<<"insertionsort的运行时间:"<cout<<"quicksort的运行时间:"<break;
case 0: break;
default: cout<<"错误！请输入正确的功能序号!"<}
}
}
算法连载（2）--快速排序与插入排序的比较 - Compower Studio - CSD... 选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法，而冒泡排序、插入排序、归并排序和基数排序是稳定的排序算法。 各种排序算法的比较（转） [转载]排序算法----分配排序（箱排序，基数排序，比较） 各种排序算法的比较 快速排序算法 快速排序算法 快速排序算法 算法设计与分析 2.81 快速排序 采用部分快速排序算法实现数组的部分排序 第三十四课 插入排序、快速排序 常见的排序算法 常用的排序算法 排序算法 采用部分快速排序算法实现数组的部分排序 - eaglet的专栏 - CSDN博客 采用部分快速排序算法实现数组的部分排序 - eaglet - 博客园 计算名次与按名次排序问题的算法优化 快速排序与快速选择算法(quick sort and quick select algor... 快速排序 算法设计与分析　冒泡排序 java排序算法 - 大海的专栏 - CSDNBlog 排序算法小结 - ilibaba的专栏 - CSDNBlog 排序算法总结 排序算法小结