数据结构实验报告课程名：数据结构课程设计任课教师：梁作娟姓名：甘言海院系：信息科学与工程学院专业年级：2010级计算机信息保密数据结构实验报告一、实验目的1.熟练掌握几种内部排序算法并比较他们效率的高低。
2.学会运用统计的方法评价算法的好坏。
3.初步理解高效排序算法的思想，掌握几种基本的算法设计技巧。
4.学会分析算法复杂度，尝试进行算法的优化处理。
5.感受算法优劣对计算速度的影响。
二、实验要求1、用Visual C++实现冒泡排序、简单选择排序、直接插入排序、快速排序、希尔排序、堆排序、折半插入排序共七种排序算法。
2、每次至少用100000个数据对每种排序算法进行测试，实验用的数据不少于五组，比较各种排序算法的效率高低，将排序结果写入文件。
三、实验方法1、使用VC6.0创建一个windows窗体应用程序，在窗体上添加9个按钮控件和一个文本框控件。
2、9个按钮控件分别代表7种排序方法以及重新生成随机数和按从大到小的顺序生成数列两个方法，用户单击其中任何一个按钮都将调用其中一个方法。
3、文本框用于显示排序所用的时间。
4、每种排序算法在完成排序后都将排序结果写入特定的文件，文件名取排序算法的名称。
四、实验内容1、打开Visual C++，创建一个新的基于对话框的MFC窗体应用程序，在生成的窗体上添加11个按钮控件和一个文本框控件，并修改11个按钮控件标签为“冒泡排序”、“简单选择”、“直接插入”、“快速排序”、“希尔排序”、“堆排序”、“折半插入”、“从小到大”、“从大到小”、“随机生成”、“清空文本框”。
2、添加头文件head.h，并在其中添加宏定义#define Num 100000，作为要排序的数据个数。
3、在窗体的类定义中添加公共属性arry和arry1，arry是要排序的数组首地址，其定义为long arry[Num+1]，在窗体的构造函数中以随机序列的方式对arry 进行初始化，通过重置函数也可以对arry数组重新赋值，重置函数有三个，可以通过点击按钮“从小到大”、“从大到小”或者“随机生成”来调用，分别以三种不同的方式给数组重新赋值。
arry1是和arry同类型的数组首地址，arry1作为arry的副本，在每次进行排序时都首先将arry数组中的值原样复制到arry1中，然后对arry1进行排序，这样就能保证arry数组的值保持不变。
4、为添加的11个按钮控件添加事件处理程序，分别为7个排序算法、3个重置函数和1个用于清空文本框的函数，三个重置函数分别以“从小到大”、“从大到小”和“随机”的方式对arry数组重新赋值。
5、修改编译器默认堆栈的大小以满足快速排序的要求，编译并连接程序，逐步修改程序中的错误，直到程序能够连接成功。
6、 运行程序，分别用7种排序算法对生成的含有100000个数据的伪随机序列进行排序，对每种排序算法记录下排序时间。
然后单击“随机生成”，换一组随机序列重新进行，同样的操作进行5遍，求各种算法排序时间的平均值。
7、 单击“从小到大”按钮，按从小到大的顺序对arry 数组赋值，然后用这个有序的数组对七种排序算法进行测试，对每种排序算法记录下排序时间，同样进行五次，求每种排序算法所用时间的平均值。
8、 最后单击“从大到小”按钮，产生按从大到小的顺序排列的数列，再次对七种排序算法进行测试，每次记下排序时间，同样的操作进行五次求平均值。
9、 在头文件head.h 中将宏定义更改为#define Num 300000，重新进行实验，对比观察排序算法对数据量的敏感程度。
10、 按照前面几步的实验结果绘制图表，比较七种排序算法的效率高低。
五、实验结果1、 程序运行效果截图2、 乱序排序时间表冒泡排序 简单选择排序 直接插入排序 快速排序 希尔排序 堆排序 折半插入排序 第一次 81.406 37.375 21.234 0.063 0.500 0.062 20.703 第二次 81.766 34.187 19.875 0.062 0.578 0.063 21.422 第三次 80.453 34.313 21.172 0.063 0.625 0.063 22.125 第四次 76.562 36.359 20.016 0.062 0.828 0.062 35.078 第五次 60.593 25.672 14.625 0.016 0.359 0.031 15.719 平均 76.15633.581 19.384 0.0530.5780.05623.009表一（数据量10万）排序方法时 间 (s) 次数冒泡排序 简单选择排序 直接插入排序 快速排序 希尔排序 堆排序 折半插入排序 第一次 556.281 223.609 135.469 0.078 3.437 0.110 142.109 第二次 550.453 237.734 133.422 0.078 3.344 0.109 144.218 第三次 543.781 228.281 136.281 0.078 3.531 0.109 151.109 第四次 484.468 236.328 141.500 0.094 3.672 0.125 146.672 第五次 581.672 232.672 143.312 0.110 3.797 0.109 147.500 平均543.331231.725 137.997 0.0883.5560.112146.322表二（数据量30万）100200300400500600时间（秒）1030数据量（万）乱序排序时间柱状图冒泡排序简单选择排序直接插入排序快速排序希尔排序堆排序折半插入排序3、 顺序排序时间表冒泡排序 简单选择排序 直接插入排序 快速排序 希尔排序堆排序折半插入排序 第一次 0.000 24.188 0.000 24.156 0.000 0.016 0.000 第二次 0.000 23.907 0.000 24.968 0.000 0.016 0.000 第三次 0.016 24.375 0.000 25.515 0.000 0.016 0.000 第四次 0.000 24.219 0.000 25.609 0.000 0.015 0.000 第五次 0.000 24.234 0.000 25.750 0.000 0.015 0.016 平均0.003 24.1850.000 25.200 0.000 0.015 0.003 表三（数据量10万）冒泡排序 简单选择排序 直接插入排序 快速排序 希尔排序堆排序 折半插入排序 第一次 0.000 225.531 0.000 224.359 0.0000.078 0.031 第二次 0.000 220.897 0.000 221.034 0.000 0.078 0.031 第三次 0.001 233.152 0.000 234.828 0.000 0.078 0.031 第四次 0.000 214.512 0.002 240.010 0.000 0.079 0.031 第五次 0.000 252.062 0.000 238.844 0.000 0.078 0.031 平均0.000232.144 0.000 233.3200.0000.0780.031表四（数据量30万）排序方法时 间 (s)次数排 序 方 法 时间(s)次数排 序 方 法 时间(s)次数50100150200250时间（秒）1030数据量（万）乱序排序时间柱状图冒泡排序简单选择排序直接插入排序快速排序希尔排序堆排序折半插入排序4、 逆序排序时间表冒泡排序简单选择排序 直接插入排序 快速排序 希尔排序堆排序折半插入排序 第一次 63.250 39.516 29.843 27.578 0.454 0.047 33.828 第二次 62.890 39.218 29.891 29.234 0.672 0.047 34.516 第三次 57.422 35.968 28.656 23.750 0.671 0.047 34.547 第四次 61.141 36.984 31.563 26.421 0.672 0.047 34.110 第五次 66.656 37.969 29.906 24.594 0.672 0.047 32.891 平均62.272 37.93129.972 26.315 0.628 0.047 33.978 表五（数据量10万）冒泡排序 简单选择排序 直接插入排序 快速排序 希尔排序堆排序 折半插入排序 第一次 578.141 248.157 290.891 233.968 7.9530.094 306.313 第二次 552.078 240.688 264.344 214.828 6.750 0.078 282.906 第三次 554.045 245.230 280.783 230.234 7.822 0.090 302.208 第四次 560.788 246.344 276.355 220.788 7.052 0.080 298.420 第五次 556.922 228.797 279.109 220.344 8.203 0.078 295.687 平均562.380239.214 278.115 223.0477.6350.083298.846表六（数据量30万）排 序方 法时 间 (s) 次数排 序 方 法 时间(s)次数100200300400500600时间（秒）1030数据量（万）乱序排序时间柱状图冒泡排序简单选择排序直接插入排序快速排序希尔排序堆排序折半插入排序六、实验结果分析1、 对乱序来说排序效率最高的是快速排序和堆排序，其次是希尔排序，然后是直接插入排序和折半插入排序，然后是简单选择排序，最慢的是冒泡排序。
2、 对于已经按从小到大的顺序排列好的数列，冒泡排序、直接插入排序、希尔排序、折半插入排序，基本不需要花费任何时间，堆排序需要少量时间，简单选择排序和快速排序效率较低。
3、 对于逆序来说，效率最高的是堆排序，其次是希尔排序，然后快速排序、简单选择排序、直接插入排序、折半插入排序的效率相差很小，冒泡排序的效率最低。
4、 综合来看堆排序、快速排序和希尔排序是较好的排序算法，对各种序列进行排序的效率都很高。
5、 快速排序由于采用递归函数的方法实现，在运行时由于编译器分配的栈的大小的限制，递归调用的层数受到限制。
在对顺序和逆序的数列进行排序时由于需要递归调用的层数比较多，程序运行可能会被意外终止，可以在调试之前通过设置编译器的堆栈大小来满足快速排序的需要。
6、 快速排序对乱序的排序效率非常高，但是对于顺序或者逆序的序列来说，排序所需时间较大，但这种情况出现的可能性较低，所以从统计的角度来讲，它仍是一种高效的排序方法，其效率和堆排序相当。