排序算法性能分析

《排序算法性能分析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、*******************实践教学*******************兰州理工大学计算机与通信学院2011年春季学期数据结构课程设计题目：专业班级：姓名：学号：指导教师：成绩：_____________________15目录摘要3前言4正文51.采用类c语言定义相关的数据类型52.各模块的伪码算法53.函数的调用关系图64.调试分析7a、调试中遇到的问题及对问题的解决方法7b、算法的时间复杂度和空间复杂度75.源程序8总结13参考文献14致谢1515摘要排序是计算机程序设计中的一种

2、重要操作。各种部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。关键字：排序，性能分析。15前言排序是计算机程序设计中的一种重要操作。它的功能是将一个数据元素的任意序列，重新排列成一个按关键字有序的序列。内部排序的方法很多，但是就其全面性能而言，很难提出一种被认为是最好的方法，每一种方法都有各自的优缺点，适合在不同的环境下使用。如果按排序过程中依据的不同原则对内部排序方法进行分类，则大致可分为插入排序，交换排序，选择排序，归并排序和记数排序等五类。这几种排序算法是在顺序存储结

3、构上实现的，因此在排序过程中需要进行大量记录的移动。当记录很大时，时间耗费很大，此时可采用静态链表作存储结构。但是有的排序方法，无法实现表排序。在这种情况下可以进行地址排序，即另设一个地址向量指示相应记录。15正文1.采用类c语言定义相关的数据类型int整型，char字符型，2.各模块的伪码算法（1）插入排序伪码算法：voidInsertSort(Splist&L){for(i=2;i<=L.length;++i)if(LT(L.r[i].key,L.r[i-1].key))　　／／“《”，须将Ｌ

4、.r[i]插入有序子表{L.r[0]=L.r[i];　　　　　　　　　／／复制为哨兵L.r[i]=L.r[i-1];For(j)i-2;LT(L.r[0].key,L.r[j].key);--j)L.r[j+1]=L.r[j];　　　　　　　　　／／记录后移L.r[j+1]=L.r[0];／／插入到正确位置}}//InsertSort(2)希尔排序voidshllInsert(Splist&L,intdk){for(i=dk+1;i<=L.length;++i)if(LT(L.r[i].key,L

5、.r[i-dk].key))　{L.r[0]=L.r[i];　　　　　　　　　　　／／暂存for(j=i-dk;j>0&<(L.r0].key,L.r[j].key);j-=dk)L.r[j+dk]=L.r[j];　　　　　　　／／记录后移L.r[j+dk]=L.r[0];}／／插入}//shellsortvoidshllsort(Splist&L,intdata[],intt){for(k=0;k

6、intpart(sqlist&L,intlow,inthigh){／／交换顺序表Ｌ中子表Ｌ。R[low..high]的记录，使枢轴记录到位，并返回其所在位　／／　此时在它之前（后）的记录均不大（小）于它。pivotkey=L.[Low].key;15while(loe=pivotkey)--high;L.r[lowL.r[high];while(low=pivotkey)++low;L

7、.r[lowL.r[high];}returnlow}//partition(4)选择排序voidselectsort(splist&L){for(i=1;i=i+1;j--)if(r[j].key

8、key)／／比较{　　　　W=r[j];R[j]=r[j-1];R[j-1]=w;}3.函数的调用关系图MainInsertionsortquicksortbubblesortselectionsortshellsortOutputquick154.调试分析a、调试中遇到的问题及对问题的解决方法刚开始进行输入时，对有些排序不能实现，我就对不能实现的排序进行分析，对产生的语法错误进行了及时的改正，以至所有的排序算法能够顺利的实现。b、算法的时间复杂度和空间复杂度算法的时间复杂度分别是