首页 > 代码库 > 归并与快速排序算法对处理同等规模的数据的对比
归并与快速排序算法对处理同等规模的数据的对比
用长分别为100、200、300、400、500、600、700、800、900、1000的10个数组的排列来统计这两种算法的时间复杂性；
快速排序程序：
#include<iostream>using namespace std;int circle;static int num[11]={0,0,0,0,0,0,0,0,0,0,0};void vector_initial(int *array,int n);void vector_print(int *array,int n);void fast_sort(int *array,int p,int r);int separate_2part(int *array,int p,int r);void count();int main(){ int a[1000]; int n; //cout<<"输入数的个数："; //cin>>n; for(circle=1;circle<=10;circle++) { vector_initial(a,circle); fast_sort(a,0,100*circle-1); vector_print(a,100*circle); } for(int i=1;i<=10;i++) cout<<i*100<<"个数据，执行步骤:"<<num[i]<<endl; return 0;}void vector_initial(int *array,int n){ int i=0; while(i<n*100) { array[i]=rand()%1000; i++; }}void vector_print(int *array,int n){ for(int i=0;i<n;i++) cout<<array[i]<<" "; cout<<endl<<endl;}void fast_sort(int *array,int p,int r){ int q; if(p<r) { q=separate_2part(array,p,r); fast_sort(array,p,q-1); fast_sort(array,q+1,r); }}int separate_2part(int *array,int p,int r){ int n1,n2,x; n1=p; n2=r; x=array[p]; while(1) { while(array[++n1]<x) { count(); } while(array[n2]>x) { count(); n2--; } if(n1>=n2) break; swap(array[n1],array[n2]); } for(int i=p+1;i<=n2;i++) { array[i-1]=array[i]; } array[n2]=x; return n2;}void count(){ switch(circle) { case 1: num[1]++; break; case 2: num[2]++; break; case 3: num[3]++; break; case 4: num[4]++; break; case 5: num[5]++; break; case 6: num[6]++; break; case 7: num[7]++; break; case 8: num[8]++; break; case 9: num[9]++; break; case 10: num[10]++; break; default: break; }}归并测试：
#include<iostream>#include<time.h>using namespace std;int a[1000];int circle;static int num[11]={0,0,0,0,0,0,0,0,0,0,0};void vector_initial(int n);void print_vector(int circle);void MERGE_sort(int p,int r);void MERGE_combine(int p,int q,int r);int main(){ for(circle=1;circle<=10;circle++) { vector_initial(circle); MERGE_sort(0,circle*100-1); print_vector(circle*100); } for(int i=1;i<=10;i++) cout<<i*100<<"个数据，执行步骤:"<<num[i]<<endl; return 0;}void vector_initial(int n){ int i=0; while(i<n*100) { a[i]=rand()%1000; i++; }}void print_vector(int n){ for(int i=0;i<n;i++) { cout<<a[i]<<" "; //if(19==i%20) // cout<<endl; } cout<<endl<<endl<<endl;}void MERGE_sort(int p,int r)//归并排序{ int q; if(p<r) { q=(p+r)/2; MERGE_sort(p,q); MERGE_sort(q+1,r); MERGE_combine(p,q,r); }}void MERGE_combine(int p,int q,int r){ int L[1000]; int R[1000]; int n1=q-p+1; int n2=r-q; for(int i=1;i<=n1;i++) L[i]=a[p+i-1]; for(int j=1;j<=n2;j++) R[j]=a[q+j]; L[n1+1]=100000; R[n2+1]=100000; i=1;j=1; for (int k=p;k<=r;k++) { switch(circle) { case 1: num[1]++; break; case 2: num[2]++; break; case 3: num[3]++; break; case 4: num[4]++; break; case 5: num[5]++; break; case 6: num[6]++; break; case 7: num[7]++; break; case 8: num[8]++; break; case 9: num[9]++; break; case 10: num[10]++; break; default: break; } if(L[i]<=R[j]) { a[k]=L[i]; i++; } else { a[k]=R[j]; j++; } }}测试结果对比：
归并算法
快速排序算法：
归并与快速排序算法对处理同等规模的数据的对比
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。