快速排序和归并排序得比较,快排比归并慢很多

C++语言 码拜 8年前 (2017-05-07) 2223次浏览
这是本人的代码:
#include<iostream>
#include<stdlib.h>
#include<time.h>
using namespace std;
void merge(int A[],int low,int mid,int high);
void mergesort(int A[],int low,int high);
void split(int A[],int low,int high,int &w);
void quicksort(int A[],int low,int high);
void showsort(int A[],int low,int high);
int a[100001]; //进行排序的数组
int b[100001]; //辅助存储的数组
int B[100001]; //用于归并排序中辅助存储的数组
int count_merge = 0; //计算归并排序的比较次数,并初始化为0
int count_quick = 0; //计算快速排序的比较次数,并初始化为0
int main()
{
double t1,t2;
double t;
int i,n;
cout << “****************************************************************” << endl;
cout << “the comparation of average time between mergesort and quicksort” << endl;
cout << “****************************************************************” << endl;
cout << “please input your choice(0-2):” << endl;
cout << “0–quit…” << endl;
cout << “1–Generate random instance” << endl;
cout << “2–Input instance” << endl;
int choice;
cin >> choice;
switch(choice)
{
case(0):exit(0); break ;
case(1):
{
double mergetime = 0;
double quicktime = 0;
int num;
cout << endl;
cout << “please input the number of arrays to sort: ” <<endl; //输入进行排序的数组个数
cin>>num;
//手动输入数据
cout<<“if manual input datas?(Y/N)”;//能否手动输入数据
char R;
cin>>R;
if(R==”Y”||R==”y”)
{
for(int d=0;d<num;d++)
{
cout << “the number of datas in Group ” << d+1 << ” is: “;
cin>>n;
for(int z=1;z<=n;z++)
{
cin>>a[z];
b[z]=a[z];
}
t1=clock();
count_merge = 0;
mergesort(b,1,n);
t2=clock();
t=t2-t1;
mergetime=mergetime+t;  // 计算归并的总时间
//showsort(b,1,n);     //显示归并排序后的结果
cout<<“mergesort spends: “<< t <<” ms”<<endl;
cout << “the comparision number in mergesort is: ” << count_merge << endl;// mergesort的比较次数
t1=clock();
count_quick = 0;
quicksort(a,1,n);
t2=clock();
t=t2-t1;
quicktime=quicktime+t;  //计算快排的总时间
//showsort(a,1,n);      //显示快速排序后的结果
cout<<“quicksort spends: “<< t <<” ms”<<endl;
cout << “the comparision number in quicksort is:” << count_quick << endl; //quicksort的比较次数
cout<<endl;
}
cout << “the average time of mergesort: “<< (mergetime/num) << ” ms” << endl;//求mergesort的平均时间
cout << “the average time of quicksort: “<< (quicktime/num) << ” ms” << endl;//求quicksort的平均时间
cout << endl;
return 0;
}
//随机产生数据
srand((unsigned)time(NULL));
for(int j=0; j<num; j++)
{
//  i = rand()%(int)(20)+1; //产生随机数,在1~20之间
n = 100000;
for(int k=0; k<n; k++)
{
b[k] = a[k] = rand()%(int)(100001);//产生n个数,在0-100000范围内
}
//cout<<“show the not sorted arrays:”<<endl;
// showsort(b,1,n);     //显示未排序的数组
cout << “the  ” << j+1 << ”  group generates randomly ” << n << ” datas” <<endl;
t1 = clock();
count_merge = 0;
mergesort(b,1,n);
t2 = clock();
t = t2-t1;
mergetime = mergetime+t;
//cout << endl;
//showsort(b,1,n);     //显示归并排序后的结果
cout << “mergesort spends:  ” << t << ”  ms” << endl;  //mergesort花费的时间
cout << “the comparision number in mergesort is: ” << count_merge << endl;// mergesort的比较次数
t1 = clock();
count_quick = 0;
quicksort(a,1,n);
t2 = clock();
t = t2-t1;
quicktime = quicktime+t;
//showsort(a,1,n);      //显示快速排序后的结果
cout << “quicksort spends:  ” << t << ”  ms” << endl;  //quicksort花费的时间
cout << “the comparision number in quicksort is:” << count_quick << endl; //quicksort的比较次数
cout << endl;
}
cout << “the average time of mergesort: “<< (mergetime/num) << ” ms” << endl;//求mergesort的平均时间
cout << “the average time of quicksort: “<< (quicktime/num) << ” ms” << endl;//求quicksort的平均时间
cout << endl;
return 0;
};break;
default:
break;
}
}
//合并A[low„mid]和A[mid+1„high]两个数组,并进行排序
void merge(int A[],int low,int mid,int high)
{
int p,q,k;
p = low;
q = mid+1;
k = low;
while( (p<=mid) && (q<=high) )
{
count_merge++;
if( A[p]<A[q] )
{
B[k]=A[p];
p++;
}
else
{
B[k]=A[q];
q++;
}
k++;
}
if( p==(mid+1) )
{
while( (k<=high) && (q<=high) )
B[k++]=A[q++];
}
else
{
while( (k<=high) && (p<=mid) )
B[k++]=A[p++];
}
for( int i=low; i<=high; i++)
A[i]=B[i];
}
//先将整个A数组分裂成若干个数组,然后再升序排列
void mergesort(int A[],int low,int high)
{
int mid;
if( low<high )
{
mid=(low+high)/2;
mergesort(A,low,mid);
mergesort(A,mid+1,high);
merge(A,low,mid,high);
}
}
//划分元素A[low]的新位置w
void split(int A[],int low,int high,int &w)
{
int i=low;
int x=A[low];
int temp;
for(int j=(low+1); j<=high; j++)
{
count_quick++;
if(A[j]<=x)
{
i++;
if(i!=j)
{
temp=A[i];
A[i]=A[j];
A[j]=temp;
}
}
}
temp=A[low];
A[low]=A[i];
A[i]=temp;
w=i;
}
//按非降序排列的数组A中的元素
void quicksort(int A[],int low,int high)
{
int w;
if( low<high )
{
split(A,low,high,w);
quicksort(A,low,w-1);
quicksort(A,w+1,high);
}
}
//显示归并排序后的结果
void showsort(int A[],int low,int high)
{
for(int i=low; i<=high; i++)
cout<<A[i]<<” “;
cout<<endl;
}
运行结果:快速排序和归并排序得比较,快排比归并慢很多
解决方案

120

引用:
Quote: 引用:

DEBUG下没有可比性

啥意思?编程小白不懂快速排序和归并排序得比较,快排比归并慢很多

前者是调试版,后者是优化版
其次还看数据,数据能否基本有序等均有定影响


CodeBye 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明快速排序和归并排序得比较,快排比归并慢很多
喜欢 (0)
[1034331897@qq.com]
分享 (0)