快速排序和归并排序

《快速排序和归并排序》由会员分享，可在线阅读，更多相关《快速排序和归并排序（12页珍藏版）》请在装配图网上搜索。

1、实验目标：(1) 通过实验比较归并分类与快速分类算法在平均情况下哪一个更快。(2) 加深对时间复杂度概念的理解。实验任务：(1) 用C/C+语言编程实现归并分类算法6.3和快速分类算法6.6。对于快速分类，SPLIT 中的划分元素采用三者A(low), A(high), A(low+high)/2)中其值居中者。(2) 随机产生20组数据(比如n=5000i, lWiW20)。数据均属于范围(0, 105)内的整数。 对于同一组数据，运行快速分类和归并分类算法，并记录各自的运行时间(以毫秒为单位)。(3) 根据实验数据及其结果来比较快速分类和归并分类算法的平均时间,并得出结论。 实验设备及环境

2、：PC； C/C+等编程语言。实验主要步骤：(1) 明确实验目标和具体任务；(2) 理解实验所涉及的两个分类算法；(3) 编写程序实现两个分类算法；(4) 设计实验数据并运行程序、记录运行的结果；(5) 根据实验数据及其结果得出结论；实验数据及运行结果、实验结果分析及结论：一、实验数据1、在窗口中输入 10,即产生 10 组数组,并选择手动输入数据,因为手动输入数据数组中数据量太小,运行时间都是0 毫秒。归并分类与快速分类平均时间之比较 请输入你要进行排序的数组个数：10是否手动输入？ .(丫刈)Y1) 234 45 56 343 656 23 56 7634 32 3442) 223 45

3、5657 546 78 67 34 56 84 578 687 98453) 48 8 54 32 65 98 452 324) 56 87 12 35 655) 568 887 54 65 32 5556）98 65 32 12 20 4 78（7）565 87 545 65 87 23 65 48 54 21（8）59 54 54 21 548 457 659 26 60（9）59 54 21 87 45 12 35 6588 877 451（10）584 87 12 35 9 15 772、在窗口中输入20，即将随机产生20 组数据，每组有5000100000个元素，元素均属于 范围（0

4、，105）内的整数。归并分类与快速分类平均时间之比较 请输入你要进行排序的数组个数：20是否手动输入？ (V/N) N.输入“N”产生随机数据，程序附带显示数组数据功能，但是因为数据量过大，在此处不显 示。二、运行结果1、 手动输入：H旳報瑪亍報是：1045 56 343 656 23 56 7634 32 344334秒4臺32 0 Lb 5费56花56花5423354233334秒 4臺 32 0 Lb 5書.344 656 7634344 656 7634H旳報瑪亍報是：1245 5657 546 78 678:8: 7W7 费 67花67花 t t 6 p 6 p 5 0 5 0 s

5、s 5e5 k 4 ff 4 c ri 4 e 4 u4 48 0 823秒23秒34 56 84 578 687 9845546 578 687 5657 9845546 578 687 5657 9845组的報据亍報是：88 54 32 65 98 452 32费54费花化t 4 t98毫98臺87 12 35 6535 56 65 87rgesort花费：0毫秒35 56 65 87 iukwt:花费：0星秒佃组的数据个数是84 87 12 35 9 1512 15 35 77 87 5 ergesort : 0 疳?组的数据个数是65 87 545 65 87 1 23 48 54 6

6、5 65 ergesort : 0 54 6icksort花费：0 5畦且的数据个数是:9 54 54 21 548 451 26 54 54 59 60ergesort : 0 疳1 26 54 54 59 60icksort花费：0 5蛀且的数据个数是:9 54 21 87 45 122 21 35 45 54 59 ergesort : 0 疳2 21 35 45 54 59 icksort花费：0疳ergesort-Jr uicksort-Jr15:0 :0*ress any key to continue2、 随机输入第5组随机虫感共有5堕書个数据 me pge s o pt-f.-

7、IS 费匸 12 尋利:;, quicksort: 9 臺秒第磋且随机去威共有?翌聘个数据mergesortj : 17quicksort: 11 毫秒 第组随机去威共有堕聲个数据mergesort: 1 毫弹quicksort化费：0毫秒第?组随机去毎共有卿聘个数据mergesortj : 16 quicksort化费：12 毫mergesortj: 6 室: quicksort : 4 毫:第过且随机生感共有?空鲁个数据 mergesort: 43 晕秒 quicksort: 22 呈秒第4组随机虫感共有9空書个数据 mepgesoFt化费匸23晕利; quicksort: 16 毫秒第3

8、组随机虫感共有些弊0个数据 mergesort费：7 呈抄 quicksort化费：4星;秒第2组随机去威共有芋薯0个数据 me rge s o pt-f.j 费=5 晕秒, quicksort : 4 毫秒第丄丄组随机超共锂5普0个数据 me rge s o rt -f.-tj 费:5 晕秒1 quicksort: 4 臺秒第12组随机超共有咚普0个数据 me rge s o rt -f.-tj 费：14 臺利； quicksort: 10 量秒第茁组随机超共锂5普0个数据 me rge s o rt -f.-tj 费:6 晕秒1 quicksort: 4 臺秒第14组随机超共有普个数据 n

9、e rge s o rt-f.-fj 费:1 昜禾少 quicksort化费：1臺秒mergesort quicksortmergesort-i quicksort-:12.85 :8.8|SJmergesortj mergesort quicksort : 15三、实验结果分析及结论在 20 组随机数据中，发现有时候快速排序快，有时候是归并排序快，两者之间的运行时间 存在一些波动，但是从总的统计结果中可以发现，快速排序的平均运行时间明显比归并排序 花费得少，故快速排序速度比归并排序快。附录：实验代码#include#include#includeusing namespace std;voi

10、d 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 a100001;进行排序的数组int b100001;辅助存储的数组int B100001;用于归并排序中辅助存储的数组int main()int t1,t2,t;int i,n;coutnum;

11、coutvv是否手动输入？ (Y/N);char R;cinR;if(R=Y|R=y)for(int d=0;dn;for(int z=l;zaz;bz=az;tl=clock();mergesort(b,l,n);t2=clock();t=t2-tl;mergetime=mergetime+t;showsort(b,l,n);/显示归并排序后的结果coutvvmergesort 花费：vvtvv毫秒vvendl;tl=clock();quicksort(a,l,n);t2=clock();t=t2-tl;quicktime=quicktime+t;showsort(a,l,n);/显示快速排

12、序后的结果coutvvquicksort 花费：vvtvv毫秒vvendl;coutvvcoutvvendl;ft .T T平平平平平平平平平平平平平平平平平平平平平平平平平平八*an / I coutvvmergesort 平均时间：vvmergetime/numvvendl;/求 mergesort 的平均时间 coutvvquicksort 平均时间：vvquicktime/numvvendl;/求 quicksort 的平均时间coutvv*vvendl;return 0;srand(unsigned)time(NULL);for(int j=0;jnum;j+)i=rand()%(i

13、nt)(20)+1;n=5000*i;for(int k=0;k=n;k+)bk=ak=rand()%(int)(100001);/产生 n 个数，在 0-100000 范围内/coutvv显示未排序的数组：vvendl;/showsort(b,1,n);/显示未排序的数组coutvv第vvj+1vv组随机生成共有vvnvv个数据vvendl;t1=clock();mergesort(b,1,n);t2=clock();t=t2-t1;mergetime=mergetime+t;/coutvvendl;/showsort(b,1,n);/显示归并排序后的结果coutvvmergesort 花费

14、：vvtvv毫秒vvendl;t1=clock();quicksort(a,1,n);t2=clock();t=t2-t1;quicktime=quicktime+t;/coutvvendl;/showsort(a,1,n);/显示快速排序后的结果 coutvvquicksort 花费：vvtvv毫秒vvendl;coutendl;cout!*1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* ft .T T平平平平平平平平平平平平平平平平平平平平平平平平平平八*an / I coutvvmergesort 平均时间：v

15、vmergetime/numvvendl;/求 mergesort 的平均时间 coutvvquicksort 平均时间：vvquicktime/numvvendl;/求 quicksort 的平均时间cout*endl;return 0;合并Alowmid和Amid+lhigh两个数组，并进行排序 void merge(int A,int low,int mid,int high)int p,q,k;p=low;q=mid+l;k=low;while(p=mid)&(q=high)if(ApAq)Bk=Ap;p+;elseBk=Aq;q+;k+;if(p=(mid+1)while(k=hig

16、h)&(q=high)Bk+=Aq+;elsewhile(k=high)&(p=mid)Bk+=Ap+;for(int i=low;i=high;i+)Ai=Bi;先将整个A数组分裂成若干个数组，然后再升序排列void mergesort(int A,int low,int high)int mid;if(lowhigh)mid=(low+high)/2;mergesort(A,low,mid);mergesort(A,mid+1,high);merge(A,low,mid,high);划分元素Alow的新位置wvoid split(int A,int low,int high,int &w)

17、int i=low;int x=Alow;int temp;for(int j=(low+1);j=high;j+)if(Aj=x)i+;if(i!=j)temp=Ai;Ai=Aj;Aj=temp;temp=Alow;Alow=Ai;Ai=temp; w=i;按非降序排列的数组A中的元素void quicksort(int A,int low,int high)int w;if(lowhigh)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+) coutAi ;coutendl;