《排序算法性能分析报告》由会员分享，可在线阅读，更多相关《排序算法性能分析报告（15页珍藏版）》请在金锄头文库上搜索。
1、 . . . . . . . * 实践教学实践教学 * 理工大学理工大学 计算机与通信学院 2011 年春季学期 数据结构数据结构课程设计课程设计 题 目： 专业班级： 姓 名： 学 号： 指导教师： 成 绩：_ . . . . . . . 目目 录录 摘要.3 前言.4 正文.5 1.1. 采用类采用类C C语言定义相关的数据类型语言定义相关的数据类型 .5 5 2.2. 各模块的伪码算法各模块的伪码算法 .5 5 3.3. 函数的调用关系图函数的调用关系图 .6 6 4.4. 调试分析调试分析 .7 7 a a、 调试中遇到的问题及对问题的解决方法调试中遇到的问题及对问题的解决方法.7 7
2、 b b、 算法的时间复杂度和空间复杂度算法的时间复杂度和空间复杂度.7 7 5.5. 源程序源程序 .8 8 总结.13 参考文献.14 致 .15 . . . . . . . 摘要摘要 排序是计算机程序设计中的一种重要操作。各种部排序算法的时间复杂度 分析结果只给出了算法执行时间的阶，或大概执行时间。 关键字：排序，性能分析。 . . . . . . . 前言前言 排序是计算机程序设计中的一种重要操作。它的功能是将一个数据元素的任 意序列，重新排列成一个按关键字有序的序列。部排序的方法很多，但是就其 全面性能而言，很难 提出一种被认为是最好的方法，每一种方法都有各自的优 缺点，适合在不同的
3、环境下使用。如果按排序过程中依据的不同原则对部排序 方法进行分类，则大致可分为插入排序，交换排序，选择排序，归并排序和记 数排序等五类。 这几种排序算法是在顺序存储结构上实现的，因此在排序过程中需要进行 大量记录的移动。当记录很大时，时间耗费很大，此时可采用静态链表作存储 结构。但是有的排序方法，无法实现表排序。在这种情况下可以进行地址排序， 即另设一个地址向量指示相应记录。 . . . . . . . 正文 1.1. 采用类采用类 c c 语言定义相关的数据类型语言定义相关的数据类型 int 整型， char 字符型， 2.2. 各模块的伪码算法各模块的伪码算法 （1）插入排序伪码算法： v
4、oid InsertSort(Splisti=L.length;+i) if(LT(L.ri.key,L.ri-1.key)“” ，须将.ri插 入有序子表 L.r0= L.ri;复制为哨兵 L.ri= L.ri-1; For(j)i-2;LT(L.r0.key,L.rj.key);-j) L.rj+1= L.rj;记录后移 L.rj+1= L.r0; 插入到正确位置 /InsertSort (2) 希尔排序 void shllInsert(Splist i0j-=dk) L.rj+dk=L.rj;记录后移 L.rj+dk=L.r0; 插入 /shellsort void shllsort (
5、Splist kt;+k) shllInsert(L,datak); /shellsort （3）快速排序 int part(sqlist . . . . . . . while(loehigh) While(low=pivotkey) -high; L.rlow L.rhigh; while(low=pivotkey) +low; L.rlow L.rhigh; return low /partition (4) 选择排序 void selectsort(splistiL.length;+i) j=selectMinKey(L,i); if(i!=j) L.ri L.rj; /selects
6、ort （5）其泡排序 void bubblesort(sqlist r,int n) int I,j,w; for (i=1;i=i+1;j-) if(rj.keyrj-1.key) 比较 W=rj; Rj=rj-1; Rj-1=w; 3.3. 函数的调用关系图函数的调用关系图 Main Insertion sort quick sort bubble sort selection sort shell sort Output quick . . . . . . . 4.4. 调试分析调试分析 a、 调试中遇到的问题及对问题的解决方法 刚开始进行输入时，对有些排序不能实现，我就对不能实现的排
7、序 进行分析，对产生的语法错误进行了及时的改正，以至所有的排序算法能 够顺利的实现。 b、 算法的时间复杂度和空间复杂度 算法的时间复杂度分别是O(n2)， O(nlog2n)，O(log2n)， 测试结果： 23 45 6 13 81 . . . . . . . 32 12 45 3 9 46 37 100 20 0 5.5. 源程序源程序 #include #include #define N 100/定义数组最大为 100 const int t=3;/定义希尔排序次数 int d3=4,3,1;/定义希尔排序比较量 int qmt;/快速排序的移动次数 int qct;/快速排序的比较
8、次数 void output(int n,int a,int ct,int mt)/部排序中调用的输出函数 int i; printf(n 排序结果:); for( i=0;in;i+) printf(%d ,ai);/输出各排序完成的数组 printf(n 比较次数:%dn,ct);/输出各排序比较次数 . . . . . . . printf(移动次数:%dnn,mt);/输出各排序移动次数 void bubble_sort(int n,int A)/冒泡排序 int mt=0;/移动次数 mt=movetime int ct=0;/比较次数 ct=cmdtime int i,j,temp
9、; int aN; for(i=0;in;i+) ai=Ai;/使数组 a与数组 A完全相同,对数组 a进行 操作(不改动 A,可以使 A被其他函数调用) for(i=0;in-1;i+) for(j=0;jn-1-i;j+,ct+) if(aj+1aj)/前后比较 temp=aj, aj=aj+1, aj+1=temp, mt+=3;/关键字交换计为 3 次移动 printf(冒泡排序); output(n,a,ct,mt); void selection_sort(int n,int A)/选择排序 int mt=0;/移动次数 movetime int ct=0;/比较次数 cmdtim
10、e int i,j,temp,k; int aN; for(i=0;in;i+) ai=Ai;/使数组 a与数组 A完全相同,对数组 a进行 操作(不改动 A,可以使 A被其他函数调用) for(i=0;in-1;i+) k=i; for(j=i+1;jaj) k=j; temp=ai, ai=ak, . . . . . . . ak=temp, mt+=3;/关键字交换计为 3 次移动 printf(选择排序); output(n,a,ct,mt); void quick(int a,int low,int up)/快速排序递归算法 int i,j,temp; if(lowup) i=low; j=up; temp=alow, qmt+; while(i!=j) qct+; while(itemp) j-, qct+; if(ij) ai+=aj, qct+; qmt+; while(ij if(ij) aj-=ai, qct+,
