发布时间 : 星期二 文章数据结构实验报告——排序更新完毕开始阅读c0a78a39a9114431b90d6c85ec3a87c240288a9e
据情况下的移动次数和交换次数。在分别运行乱序、顺序和逆序数组排序时取出前两个数组的值写入第三个数组，然后置零继续统计。 C++实现： 请参看源代码。
时间复杂度与空间复杂度：
理论分析可以得出各种排序算法的时间复杂度和空间复杂度，如下表所示：
排序方法 直接插入排序 希尔排序 起泡排序 快速排序 简单选择排序 堆排序 归并排序
平均情况 O(n2) 最好情况 O(n) O(n1.3) 最坏情况 O(n2) O(n2) O(n2) O(n2) O(n2) 辅助空间 O(1) O(nlog2n)~O(n2) O(n2) O(1) O (n) O(1) O(nlog2n) O(n2) O(nlog2n) O(n2) O(log2n) ~O(n) O(1) O(nlog2n) O(nlog2n) O (nlog2n) O(1) O(nlog2n) O(nlog2n) O(nlog2n) O(n) 5
3. 程序运行结果 程序运行框图：
6 实际测试和分析：
实际运行结果如下：（其中随机产生的数据量为1000）
图一 加入了次数统计的运行结果
图二 没有加入次数统计的运行结果
作如下分析：
1、 多次运行之后统计，从乱序的时间消耗来看，基本符合理论分析。参看图一。 2、 由于加入了统计次数的代码，势必增加时间开销，这样统计出来的时间将有一定的误差。
假若比较次数和移动次数相差较多，则将产生较大的实验误差。故重新写了代码，没有加入比较次数和移动次数的比较的代码，运行结果如图二所示，均采用随机产生的1000个乱序数据进行排序。可以看出时间有所减少。因而图二更加接近实际。 3、本程序中的代码有的采用了递归的形式，如果考虑用栈来模拟的话，效率会有提升，所以运行时间还和代码的实现有关，代码本身只是描述了算法思想，并没有再进行编写方面的优化，因而还不能完全反映出每个算法的根本性能。
7 4. 总结
1、在初期构思代码的时候，首先构造了各种算法的基本实现代码，封装成类，已经能够实现七种排序的基本功能，并且测试无误。后来考虑能否优化本程序，首先考虑到测试算法的需求，需要大量随机数，因为增添了随机函数发生器，满足各种测试条件的需求。之后考虑如何能简化代码以实现多达七种排序算法的简单调用、乱序和顺序以及逆序数据的分别排序和性能指标统计、算法时间的精确而简易的统计、算法移动次数和比较次数的精确统计。如果设计不合理，将使得主调函数的调用代码冗长，可读性变差。因而采用了函数指针数组和统一的接口函数，采用二维数组存储移动次数和比较次数，调用精确的系统函数实现时间的统计。此外还添加了一些列优化，特别是函数封装的方法，使得程序的结构变得更加合理，版面风格也变得好看，可读性增强。
2、程序的优化是一个艰辛的过程，如果只是实现一般的功能，将变得容易很多，当加上优化，不论是效率还是结构优化，都需要精心设计。这次做优化的过程中，遇到不少阻力。由于优化中用到很多类的封装和访问控制方面的知识，而这部分知识恰好是大一一年学习的薄弱点。因而以后要多花力气学习C++编程语言，必须要加强这方面的训练，这样才能在将编程思想和数据结构转换为代码的时候能得心应手。
3、改进：本程序代码设计时运用了递归的调用方式，效率还可以通过将其转换为栈模拟的方式得以提高。在实现类的封装的时候为了共享数据采用了友元函数的方式，考虑能否使用其他方式使得类的封装更加完善。
8