归并排序与快速排序平均时间之比较 (C++)
程序员文章站
2022-03-24 15:29:24
...
实验名称:归并排序与快速排序平均时间之比较 (验证型实验)
实验目标:
(1) 通过实验比较归并排序与快速排序算法在平均情况下哪一个更快。
(2) 加深对时间复杂度概念的理解。
实验任务:
(1)用C/C++语言编程实现归并排序算法6.3和快速排序算法6.6。对于快速排序,SPLIT中的划分元素采用三者A(low),A(high),A((low+high)/2)中其值居中者。
(2)随机产生20组数据(比如n=5000i,1≤i≤20)。数据均属于范围(0,105)内的整数。对于同一组数据,运行快速排序和归并排序算法,并记录各自的运行时间(以毫秒为单位)。
(3)根据实验数据及其结果来比较快速排序和归并排序算法的平均时间,并得出结论。
实验设备及环境:
PC;C/C++等编程语言。
实验主要步骤:
(1) 明确实验目标和具体任务;
(2) 理解实验所涉及的两个分类算法;
(3) 编写程序实现两个分类算法;
(4) 设计实验数据并运行程序、记录运行的结果;
(5) 根据实验数据及其结果得出结论;
一、代码:
1.快速排序
int Split(int a[],int low,int high) {
int i=low,temp;
if(a[low]< a[(low+high)/2]) {
if(a[low]<a[high]) {
if(a[(low+high)/2]<a[high]) {
temp= a[(low+high)/2];
a[(low+high)/2]=a[low];
a[low]=temp;
}
else {
temp=a[high];
a[high]=a[low];
a[low]=temp;
}
}
}
else {
if(a[(low+high)/2]<a[high]) {
if(a[low]>a[high]) {
temp=a[high];
a[high]=a[low];
a[low]=temp;
}
}
else {
temp= a[(low+high)/2];
a[(low+high)/2]=a[low];
a[low]=temp;
}
}
for(int j=low+1;j<=high;j++) {
if(a[j]<a[low]) {
i++;
if(i!=j) {
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
}
temp=a[i];
a[i]=a[low];
a[low]=temp;
return i;
}
void QuickSort(int a[],int low,int high) {
if(low<high) {
int w=Split(a,low,high);
QuickSort(a,low,w-1);
QuickSort(a,w+1,high);
}
}
2.归并排序
void merge(int a[],int first,int mid,int end,int c[]) {
int pbotton=first;
int f=first,m=mid;
while(f<mid&&m<=end)
if(a[f]<a[m])
c[pbotton++]=a[f++];
else
c[pbotton++]=a[m++];
if(f==mid)
while(m<=end)
c[pbotton++]=a[m++];
else
while(f<mid)
c[pbotton++]=a[f++];
for(int i=first;i<=end;i++)
a[i]=c[i];
}
void mergeSort(int a[],int low,int high,int c[]) {
if(low<high) {
mergeSort(a,low,(low+high)/2,c);
mergeSort(a,(low+high)/2+1,high,c);
merge(a,low,(low+high)/2+1,high,c);
}
}
3.主函数
int main() {
int random=5000,j=1;
int*merge_array,*quick_array,*c;
clock_t start,end,start1,end1;
srand((int((NULL))));
cout<<"随机数数量\t归并排序时间\t快速排序算法时间"<<endl;
while(j<=20) {
merge_array=new int[random*j];
quick_array=new int[random*j];
c=new int [random*j];
for(int i=0;i<random*j;i++) {
merge_array[i]=rand();
quick_array[i]=merge_array[i];
}
start=clock();
mergeSort(merge_array,0,random*j-1,c);
end=clock();
delete []merge_array;
start1=clock();
QuickSort(quick_array,0,random*j-1);
end1=clock();
delete []quick_array;
delete []c;
cout<<random*j<<"\t\t"<<static_cast<double>(end-start)/CLOCKS_PER_SEC*1000<<"ms\t\t";
cout<<static_cast<double>(end1-start1)/CLOCKS_PER_SEC*1000<<"ms"<<endl;
j++;
}
return 0;
}
二、实验过程和实验结果分析
截图如下
采用的是让程序产生随机数进行排序的方法。随机产生20组0到100的数(random=5000i,1≤i≤20)。对于同一组数据,运行快速排序和归并排序算法。
由三次程序运行结果可以看出,当随机数数量较少的时候,归并排序和快速排序的时间差别不大,当数量逐渐增多时候,排序的时间差别开始增大,且快速排序时间少于归并排序时间。
由此可以推测出,快速排序在数据较多时比归并排序更为高效。
下一篇: C语言实现递归加法和递归阶层