《排序算法分析》由会员分享，可在线阅读，更多相关《排序算法分析（16页珍藏版）》请在金锄头文库上搜索。
1、实验报告课程名称计算机软件基础实验项目排序算法分析实验仪器VS2005系别光电信息与通信工程专 业电子信息工程班级/学号学生姓名实验日期成 绩指导教师实验五、排序算法分析1、实验目的： 掌握顺序表的常用排序方法，掌握算法性能测算技术。通过实验 测算各排序算法的性能并进行分析比较。2、实验内容：1) 分别编写函数实现插入排序、冒泡排序和快速排序算法，算 法应具有记录比较次数和移动次数的功能，以及显示每趟排 序中间结果的功能。2) 编制一个应用程序，它将随机产生的 n 个整数插入到一个顺 序表中，然后分别用上述排序算法对这个顺序表进行排序， 并显示各种方法的比较次数和移动次数；3) 取n=10,运
2、行程序，检察排序中间结果及次数统计是否正 确。选做内容：4) 修改程序，关闭算法输出中间结果的功能，然后分别以 n=50、500 和 5000 运行这个程序，对次数的统计结果作出 分析和解释。5) 利用计时函数实现对排序算法的运行时间计时。6) 分析说明：影响排序时间、比较次数及交换次数的因素有哪 些？3、实验步骤(1)插入排序:运行结果:：. C:Uocurnents anti 5ettfngsAcfministrator=面僕五次实耋读鲨代耳4219S4479528721&418撕入排臥过程,421984470528721&419194284470528721&419e1942447052
3、872i419e1942447092072i6410e1942447092072i6410s1?424452?a8721641861942445279872164186192142445270876418s192142445264708710sIS19214244S2&47087冒泡排序:运行结果:冒泡排队过程24219S447RE2872164IS1942Q447RE2872164IS19Q42447RE2872164IS19Q4244527R872164IS19Q4244527R218764IS19Q4244527R21487IS19Q4244527R2141H87a194244527R2
4、141H87a19424452217R41H87a194244522147B1H87a19424452214IB7R87a19424421E24IB7R87a19424421E21047R87a19422144E21047R87a1942214416E247R87a1921424416E247R87a1921421644E247R87a1921104244E247R87a1910214244E247R87a1019214244E247R87比较次数，45診动次数！ 19快速排序:运行结果:快速排队过程匕4219 垃卫 ；.9 I：卫 ；.9 I：卫 ；.9 I：:101.7:101.7:101
5、.7:LH H:LH H:LH HI： 10 刖I： 10 刖Q-Q-01_s4444442121212121212121212121212121212121212121212121212121217B 52 7R 527R 527R 527R 527R 5270 F242 F242524252425242524252425242524252425242524244424442444244424442444244424442444244424442447 B7 B7 B7 H7 H7 S7搐S7S78787K7K7K7 7 7 7 S7 S7 B7 52 52 52 52 S2 S2 52 S
6、22121212170707(?7(?7R?0?0?0?070707070707070707070444646464646464646464646464646464646464646464646444444470 ?(?(? ?fii1B104444444444444444444444444444444444S7S7 a? a? a? a? a? 汕ress anu keytoi Qi 61 if!UC比较次数统计与分析n=501人始入较动腿过总秋数:：514鬻腿过宅土较次数:-226凄謝茨数:：1483fess anu key to continuen=500数程需 个过 记数整八次 入始入
7、较动 厶MLJn_宙匕多比较次数 4661 誘窃庆数 222E；Press any Kuy to continuen=5000输入记录个数；破恥 原始数据； 齢媲过凰 比较次数二6195050 移动次教二6200049鲫过山移动次数；6190051决速排队过程三確次数;169386 穆动次熟24944”iress 盘n于 ke/ to continue通过比较可以看出，快速排序效率最高，而且排序数列越多越能显示 其效率，冒泡排序和插入排序移动次数相差不大，但是比较次数相差 相当大，所以平均来说，冒泡排序的时间复杂度最高，插入排序时间 复杂度居中，快速排序最小。F面的截图更能说明这一点:I 膠动
8、次数F . 时间=1S7-00cqii t inite2291229由图中我们可以发现，快速排序所花时间最少，插入排序次之，冒泡 排序最慢。影响排序时间、比较次数和移动次数的主要因素有待排序的数据记录 数目、序列的初始状态等等。4、程序清单#include #include #include #define M 5000 /M为待排序记录的最大数目struct record int key;int otheritem;typedef struct record RECORD;long comp;/比较次数long move;/移动次数void printfile(RECORD R,int n)
9、/输出数列int i;for (i=0;in;i+)if(Ri.key10)printf( ); printf( %d,Ri.key);printf(n);void insertsort(RECORD R,int n)/插入排序 int i, j;RECORD temp;for(i=1;in;i+) temp=Ri;j=i-1;comp+;while(temp.key=0)Rj+1=Rj;move+;comp+;j-;Rj+1=temp;move+=2;printfile(R,n);/显示中间排序结果void bubblesort(RECORD R, int n)/修改算法,加入比较次数和移动
10、次数统计,以及显示中间排序结果int i,j,flag;RECORD temp;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);/显示中间排序结果int qpass(RECORD R,int n, int low, int high)/修改算法,加入比较次数和移动次数统计int i, j, k;RECORD x;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)comp+;/比较次数Rj=Ri;move+; /移动次数printfile(R,n);/显示中间排序结果Ri=x;return(i);void quicksort(RECORD R, int n, int low, int high)/ 快速排序int i;if (lowhigh)i=qpass(R,n,low,high);quicksort(R,n,low,i-1);/递归调用quicksort(R,n,i
