北邮数据结构实验四-排序

cout << \选择排序： Compare：\ Move：\

setw(3) << MoveCount << \ Time: \}

各种排序方法理论值统计结果：

排序方法 直接插入排序 冒泡排序 快速排序 简单选择排序

平均情况 O(n2) O(n2) 最好情况 O(n) 最坏情况 O(n2) O(n2) O(n2) O(n2) 辅助空间 O(1) O (n) O(1) O(log2n) ~O(n) O(1) O(nlog2n) O(n2) O(nlog2n) O(n2) 3. 程序运行结果

输出统计结果 开始 产生顺序数组，四种排序和统计 产生逆序数组，四种排序和统计 产生随机数组，四种排序和统计

结束 实际测试和分析：（实际数据量都是10000）

对于运行结果作如下分析：

1.多次运行之后统计，从随机数列的时间消耗来看，基本符合理论分析。参看图一。

2.由于加入了统计次数的代码，势必增加时间开销，这样统计出来的时间将有一定的误差。假若比较次数和移动次数相差较多，则将产生较大的实验误差。。

3.本程序中的关于快速排序的代码有的采用了递归的形式，而考虑用栈来模拟的话，实际的效率会有提升，所以运行时间还和代码的实现方式有关，代码本身只是描述了算法思想，并没有再进行编写方面的优化，因而还不能完全反映出每个算法的根本性能。

4. 总结

1、在初期构思代码的时候，首先构造了各种算法的基本实现代码，并且通过建立单链表的方式实现排序，将函数封装成类，已经能够实现四种排序的基本功能，并且测试无误。后来考虑能否优化本程序，首先考虑到测试算法的需求，需要大量随机数，因为增添了随机函数发生器，满足各种测试条件的需求。

2、程序的优化是一个艰辛的过程，如果只是实现一般的功能，将变得容易很多，当加上优化，不论是效率还是结构优化，都需要精心设计。这次做优化的过程中，遇到不少阻力。由于优化中用到很多类的封装和访问控制方面的知识，而这部分知识恰好是以前C++学习中没有被重视的一点。因而以后要多花力气学习编程语言，必须要加强这方面的训练，这样才能在将编程思想和数据结构转换为代码的时候能得心应手。

3、改进：本程序代码设计时运用了递归的调用方式，效率还可以通过将其转换为栈模拟的方式得以提高。还有一点就是产生随机数的时候，由于在主函数中已经定义了数组的大小，故而为了防止溢出，在产生数据时数据范围有限而无法达到完全随机。这一点不足是未能在实验中弥补的。