北邮数据结构实验报告排序.doc

北京邮电大学信息与通信工程学院数据结构实验报告实验名称： 实验四排序学生姓名： 班 级： 班内序号： 学 号： 日 期： 2014年12月19日1实验要求实验目的通过实现下述实验内容，学习、实现、对比各种排序算法，掌握各种排序算法的优劣，以及各种算法使用的情况。实验内容使用简单数组实现下面各种排序算法，并进行比较。排序算法： 1、插入排序 2、希尔排序3、冒泡排序4、快速排序5、简单选择排序6、堆排序（选作）7、归并排序（选作）8、基数排序（选作）9、其他要求： 1、测试数据分成三类：正序、逆序、随机数据2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换计为3次移动）。 3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微秒（选作）4、对2和3的结果进行分析，验证上述各种算法的时间复杂度编写测试main()函数测试线性表的正确性。2. 程序分析首先，题目要求测试不同的数据，所以可以手动输入待排序元素。其次，由于对一组数据要求用不同的排序算法来处理，所以需要一个复制函数把排序前的无序数组寄存出去，为下一次排序做准备。再次，由于每次排序后都需要把排序后的结果打印出来，代码是一样的，根据相同的代码可以封装成一个函数的思想，所以还需增加一个打印函数。2.1 存储结构本程序采用简单数组来储存输入的待排序数组2.2 关键算法分析核心算法思想： 1. 利用教材讲述的基本算法思想，实现七种排序算法，统计其运行相关数据。 2. 将七种排序函数入口地址作为函数指针数组，实现快速调用和统计。使得程序代码可读 性增、结构更加优化。关键算法思想描述和实现： 关键算法1： 实现七种算法的基本排序功能。 1、 插入排序：依次将待排序的序列中的每一个记录插入到先前排序好的序列中，直到全部记录排序完毕。插入排序的思想是：每次从无序区取一元素将其添加到有序区中。2、 希尔排序：先将整个序列分割成若干个子列，分别在各个子列中运用直接插入排序，待整个序列基本有序时，再对全体记录进行一次直接插入排序。3、 冒泡排序：两两比较相邻记录的关键码，如果反序则交换，直到没有反序记录为止。4、 快速排序：首先选择一个基准，将记录分割为两部分，左支小于或等于基准，右支则大于基准，然后对两部分重复上述过程，直至整个序列排序完成。 5、 选择排序：从待排序的记录序列中选择关键码最小（或最大）的记录并将它与序列中的第一个记录交换位置；然后从不包括第一个位置上的记录序列中选择关键码最小（或最大）的记录并将它与序列中的第二个记录交换位置；如此重复，直到序列中只剩下一个记录为止。 2.3 其他时间复杂度与空间复杂度理论分析可以得出各种排序算法的时间复杂度和空间复杂度，如下表所示：排序方法平均情况最好情况最坏情况辅助空间直接插入排序O(n2)O(n)O(n2)O(1)希尔排序O(nlog2n)O(n2)O(n1.3)O(n2)O(1)起泡排序O(n2)O(n)O(n2)O(1)快速排序O(nlog2n)O(nlog2n)O(n2)O(log2n)O(n2)简单选择排O(n2)O(n2)O(n2)O(1)3. 程序运行结果程序运行框图：实际测试和分析：实际运行结果如下：1 正序排序2 倒序排序3 乱序排序4. 总结1、在初期构思代码的时候，首先构造了各种算法的基本实现代码，封装成类，已经能够实现七种排序的基本功能，并且测试无误。后来考虑能否优化本程序，首先考虑到测试算法的需求，需要大量随机数，因为增添了随机函数发生器，满足各种测试条件的需求。之后考虑如何能简化代码以实现多达七种排序算法的简单调用、乱序和顺序以及逆序数据的分别排序和性能指标统计、算法移动次数和比较次数的精确统计。如果设计不合理，将使得主调函数的调用代码冗长，可读性变差。因而采用了函数指针数组和统一的接口函数，采用二维数组存储移动次数和比较次数，调用精确的系统函数实现时间的统计。此外还添加了一些列优化，特别是函数封装的方法，使得程序的结构变得更加合理，版面风格也变得好看，可读性增强。 2、程序的优化是一个艰辛的过程，如果只是实现一般的功能，将变得容易很多，当加上优化，不论是效率还是结构优化，都需要精心设计。这次做优化的过程中，遇到不少阻力。由于优化中用到很多类的封装和访问控制方面的知识，而这部分知识恰好是大一一年学习的薄弱点。因而以后要多花力气学习C+编程语言，必须要加强这方面的训练，这样才能在将编程思想和数据结构转换为代码的时候能得心应手。