【精品】排序性能分析

《【精品】排序性能分析》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、摘要2前言3正文41・问题描述42.逻辑设计53.详细设计63.1采用类c语言定义相关的数据输入：63.2伪码算法：63.3函数调用关系图94.程序编码105.程序调试与测试126.结果分析166.1调试中遇到的问题及对问题的解决方法：166.2算法的时间复杂度和空间复杂度：16设计总结17参考文献18致谢19由于待排序的记录数量不同，使得排序过程中涉及的存储器不同，可将排序方法分为两大类：一类是内部排序；一类是外部排序。内部排序时当文件的数据量不太大、待排序的记录数不多时，排序过程中的全部记录均可放入计算机内存中完成的排序；外母排序时待排序的文件很大

2、，涉及的记录数相当多，内存不能全部容纳，在排序过程屮需对除内存之外的其他存储介质（外存）进行存取访问完成记录位置交换的排序。按排序过程屮依据的不同原则，还可将内部排序分为插入排序（如直接插入排序、折半插入排序、表插入排序、希尔排序）、交换排序（冒泡排序、快速排序）、选择排序（如简单选择排序、树形选择排序、堆排序）、归并排序（如二路归并排序）、基数排序五种类型。关键字:时间复杂度;排序;性能分析排序是计算机程序设计中的一种重要操作。它的功能是将一个数据元素的任意序列，重新排列成一个按关键字有序的序列。内部排序的方法很多，主要分为插入排序（如直接插入排序、

3、折半插入排序、表插入排序、希尔排序）、交换排序（如冒泡排序、快速排序）、选择排序（如简单选择排序、树形选择排序、堆排序）、归并排序（如二路归并排序）、基数排序五种类型。一般情况下，排序时间省和占用空间少的要求很难两全。因此，很难说那一种算法好。在评价内排序算法的时间复杂性的优劣时，通常采用最坏情况下和平均情况下的代价加以衡量。由于内排序的算法所耗费的时间与结点或记录的初始分布情况是相关的，因此仅仅考虑在最坏情况下的时间代价是不全面的。通常假定结点或记录的各种分布情况都是等可能出现的，用平均情况下的时间代价衡量算法的好坏将更加客观。每一种方法都有各自的优

4、缺点，适合在不同的环境下使用。这儿种排序算法是在顺序存储结构上实现的，因此在排序过程中需要进行大量记录的移动。当记录很大时，时间耗费很大，此时可采用静态链表作存储结构。但是有的排序方法，无法实现表排序。在这种情况下可以进行地址排序，即另设一个地址向量指示相应记录。1.问题描述对各种排序算法进行定量的性能分析。各种内部排序算法的吋间复杂度分析结果只给岀了算法执行时间的阶，或人概执行时间。试通过随机的数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。该设计要求学生演掌握各种排序的基本思想及排序算法。1.逻辑设计排序是计算机程序设计中的一种重要

5、操作。它的功能是将一个数据元素的任意序列，重新排列成一个按关键字有序的序列。内部排序的方法很多，但是就其全面性能而言，很难提出一种被认为是最好的方法,每一种方法都有各自的优缺点，适合在不同的环境下使用。如果按排序过程中依据的不同原则对内部排序方法进行分类，则人致可分为插入排序，交换排序，选择排序，归并排序和记数排序等五类。此实验通过对起泡排序、直插排序、选择排序、快速排序、归并排序这几种内部排序算法进行比较，能使我们更好的掌握这些排序的基本思想及排序算法。通过该题目的设计过程，可以加深理解各种数据结构的逻辑结构、存储结构及相应上运算的实现，进一步理解和

6、熟练掌握课本中所学的各种数据结构，学会如何把学到的知识用于解决实际问题，培养我们的动手能力。1.详细设计3.1采用类c语言定义相关的数据输入:Int整型char字符型#defineN100//定义数组最大为100constintt=3;〃定义希尔排序次数intd[3J={4,3,l}；〃定义希尔排序比较量intqmt;//快速排序的移动次数intqct;//快速排序的比较次数主要函数：voidmain()voidoutput()bubble_sort(n,A);//冒泡排序insertionsort(n,A);//插入排序selectionsort(n

7、,A);//选择排序quicksort(n,A);〃快速排序shcll_sort(n,A);//希尔排序3.2伪码算法:(1)插入排序伪码算法VoidInscrtSort(RccordnodcrE],intn){for(i=2;i<=n;++i)if(r[i]

8、;intbool;intx;d=n;do{d二[d/2];bool二1;for(i=l;i<=