排序算法分析

1、实验报告课程名称计算机软件基础实验项目排序算法分析实验仪器VS2005系别光电信息与通信工程专业电子信息工程班级/学号学生姓名实验日期成绩指导教师实验五、排序算法分析1、实验目的：掌握顺序表的常用排序方法，掌握算法性能测算技术。通过实验测算各排序算法的性能并进行分析比较。2、实验内容：分别编写函数实现插入排序、冒泡排序和快速排序算法，算法应具有记录比较次数和移动次数的功能，以及显示每趟排序中间结果的功能。编制一个应用程序，它将随机产生的n个整数插入到一个顺序表中，然后分别用上述排序算法对这个顺序表进行排序，并显示各种方法的比较次数和移动次数；取n=10,运行程序，检察排序中间结果及次数统计是否

2、正确。选做内容：修改程序，关闭算法输出中间结果的功能，然后分别以n=50、500和5000运行这个程序，对次数的统计结果作出分析和解释。利用计时函数实现对排序算法的运行时间计时。分析说明：影响排序时间、比较次数及交换次数的因素有哪些？3、实验步骤(1)插入排序:运行结果:：.C:Uocurnentsanti5ettfngsAcfministrator=面僕五次实耋读鲨代耳4219S4479528721&418撕入排臥过程,421984470528721&419194284470528721&419e1942447052872i419e1942447092072i6410e19424470920

3、72i6410s1?424452?a8721641861942445279872164186192142445270876418s192142445264708710sIS19214244S2&47087冒泡排序:运行结果:冒泡排队过程24219S447RE2872164IS1942Q447RE2872164IS19Q42447RE2872164IS19Q4244527R872164IS19Q4244527R218764IS19Q4244527R21487IS19Q4244527R2141H87a194244527R2141H87a19424452217R41H87a194244522147B

4、1H87a19424452214IB7R87a19424421E24IB7R87a19424421E21047R87a19422144E21047R87a1942214416E247R87a1921424416E247R87a1921421644E247R87a1921104244E247R87a1910214244E247R87a1019214244E247R87比较次数，45診动次数！19快速排序:运行结果:快速排队过程匕4219垃卫；.9I：卫；.9I：卫；.9I：:101.7:101.7:101.7:LHH:LHH:LHHI：10刖I：10刖Q-Q-01_s44444421212121

5、21212121212121212121212121212121212121212121217B527R527R527R527R527R5270F242F242524252425242524252425242524252425242524244424442444244424442444244424442444244424442447B7B7B7H7H7S7搐S7S78787K7K7K7777S7S7B752525252S2S252S22121212170707(?7(?7R?0?0?0?070707070707070707070444646464646464646464646464646464

6、646464646464646444444470?(?(?fii1B104444444444444444444444444444444444S7S7a?a?a?a?a?汕ressanukeytoiQi61if!UC比较次数统计与分析n=501人始入较动腿过总秋数:：514鬻腿过宅土较次数:-226凄謝茨数:：1483fessanukeytocontinuen=500数程需个过记数整八次入始入较动厶MLJn_宙匕多比较次数4661誘窃庆数222E；PressanyKuytocontinuen=5000输入记录个数；破恥原始数据；齢媲过凰比较次数二6195050移动次教二6200049鲫过山移动次

7、数；6190051决速排队过程三確次数;169386穆动次熟24944”iress盘n于ke/tocontinue通过比较可以看出，快速排序效率最高，而且排序数列越多越能显示其效率，冒泡排序和插入排序移动次数相差不大，但是比较次数相差相当大，所以平均来说，冒泡排序的时间复杂度最高，插入排序时间复杂度居中，快速排序最小。F面的截图更能说明这一点:I膠动次数F.时间=1S7-00cqiitinite2291229由图中我们可以发现，快速排序所花时间最少，插入排序次之，冒泡排序最慢。影响排序时间、比较次数和移动次数的主要因素有待排序的数据记录数目、序列的初始状态等等。4、程序清单#include#i

8、nclude#include#defineM5000/M为待排序记录的最大数目structrecordintkey;intotheritem;typedefstructrecordRECORD;longcomp;/比较次数longmove;/移动次数voidprintfile(RECORDR,intn)/输出数列inti;for(i=0;in;i+)if(Ri.key10)printf();printf(%d,Ri.key);printf(n);voidinsertsort(RECORDR,intn)/插入排序inti,j;RECORDtemp;for(i=1;in;i+)temp=Ri;j=

9、i-1;comp+;while(temp.key=0)Rj+1=Rj;move+;comp+;j-;Rj+1=temp;move+=2;printfile(R,n);/显示中间排序结果voidbubblesort(RECORDR,intn)/修改算法,加入比较次数和移动次数统计,以及显示中间排序结果inti,j,flag;i+;RECORDtemp;i=1;flag=1;while(flag)flag=0;for(j=0;jRj+1.key)temp=Rj;Rj=Rj+1;Rj+1=temp;flag=1;move+;/移动次数统计printfile(R,n);/显示中间排序结果intqpas

10、s(RECORDR,intn,intlow,inthigh)/修改算法,加入比较次数和移动次数统计inti,j,k;RECORDx;i=low;j=high;x=Rlow;k=x.key;while(ij)while(i=k)j-;comp+;/比较次数Ri=Rj;move+;/移动次数printfile(R,n);/显示中间排序结果while(ij)&(Ri.keyk)i+;comp+;/比较次数Rj=Ri;move+;/移动次数printfile(R,n);/显示中间排序结果Ri=x;return(i);voidquicksort(RECORDR,intn,intlow,inthigh)/

11、快速排序inti;if(lowhigh)i=qpass(R,n,low,high);quicksort(R,n,low,i-1);/递归调用quicksort(R,n,i+1,high);/递归调用voidmain()RECORDfileM,file1M,file2M;inti,n;clock_tstart,end;/记录起始时间和结束时间doubleduration;/记录排序时间prints输入记录个数:);scanf(%d,&n);/产生待排序文件srand(unsigned)time(NULL);for(i=0;in;i+)filei.key=rand()%100;file1i=fil

12、ei;file2i=filei;printf(原始数据:n);printfile(file,n);comp=0;move=0;printf(插入排队过程:n);/printfile(file,n);start=clock();insertsort(file,n);end=clock();duration=(double)(end-start);/显示统计结果printf(”比较次数：dn,comp);printf(”移动次数：dn,move);/插入排序起始时间/插入排序结束时间/插入排序时间comp=0;move=0;printf(冒泡排队过程:n);printfile(file1,n);s

13、tart=clock();bubblesort(file1,n);end=clock();duration=(double)(end-start);/冒泡排序起始时间/冒泡排序结束时间/冒泡排序时间/显示统计结果printf（比较次数：%dn,comp）;printf（移动次数：dn,move）;printf（时间：.2fnn,duration）;输出冒泡排序时间printf（时间：.2fnn,duration）;输出插入排序时间comp=0;move=0;prints快速排队过程:n);printfile(file2,n);start=clock();quicksort(file2,n,0,n-1);end=clock();duration=(double)(end-start);/快速排序起始时间/快速排序结束时间/快速排序时间/显示统计结果printf（”比较次数：dn,comp）;printf（移动次数：%dn,move）;printf（时间：%.2fn,duration）;/输出快速排序时间5、总结这次实验，我学会了三种排序方法，了解了它们的区别