青岛理工大学数据结构课程设计报告题目：排序综合院（系）：计算机工程学院学生姓名:班级：学号:起迄日期:指导教师:2011—2012年度第2学期一、需求分析问题描述：（1）至少采用三种方法实现上述问题求解（提示，可采用的方法有插入排序、希尔排序、冒泡排序、快速排序、选择排序、堆排序、归并排序）。并把排序后的结果保存在不同的文件中。（2）统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的方法。2.基本功能（1）显示随机数：调用Dip()函数输出数组a[]。数组a[]中保存有随机产生的随机数。（2）直接选择排序：通过n-I次关键字间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i个记录交换之。（3）冒泡排序：如果有n个数，则要进行n-1趟比较。在第1趟比较中要进行n-1次两两比较，在第j趟比较中要进行n-j次两两比较。（4）快速排序：先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。（5）直接插入排序：将一个记录插入到已排序好的有序表中，从而得到一个新的、记录数增1的有序表。设整个排序有n个数，则进行n-1趟插入，即：先将序列中的第1个记录看成是一个有序的子序列，然后从第2个记录起逐个进行插入，直至整个序列变成按关键字非递减有序列为止。希尔排序：将随机数组进行希尔排序，希尔增量dlta[k]=2^(15-k)-1.堆排序：不断对对进行筛选和构建大堆顶，并进行值得交换排序。（7）显示各排序算法排序后的的数据和时间效率，并比较找出其中2种较快的方法。3.输入输出输入是按按钮输入，分别有插入，选择，快速，冒泡，堆，希尔，效率，显示，退出按钮。输出有两个编辑框，分别显示随机数和排序时间，并能显示较快两种排序方式的时间。二、概要设计设计思路：用MFC设置界面，用各种按钮显示各种功能。使用随机种子，随机函数来产生数字并存入数组中。分别使用直接插入排序，选择排序，快速排序，冒泡，堆，希尔排序等方法进行排序，并调用高精度计数来对时间进行计算，选出较快两种方式。2.数据结构设计：ADTorderadlelist{数据对象：D={ai|ai属于整型}数据关系：R1={<a[i-1],a[i]>|a[i-1],a[i]属于D}基本操作：Bubblesort(inta[])操作结果：对数组a进行冒泡排序，返回值为空。Heapsort(inta[],intn)操作结果：对数组a进行堆排序，返回值为空。InsertSort(inta[],intn)操作结果：对数组a进行插入排序，返回值为空。Quicksort(inta[],intn)操作结果：对数组a进行快速排序，返回值为空。Selectsort(inta[])操作结果：对数组a进行选择排序，返回值为空。shellInsert(inta[],intdk)操作结果：对数组a进行希尔排序，返回值为空。Disp（inta[])操作结果：显示数据。TBubblesort(inta[])操作结果：返回冒泡排序所用的时间。Theapsort(inta[],intn)操作结果：返回堆排序所用时间。TInsertSort(inta[],intn)操作结果：返回插入排序所用时间。TQuicksort(inta[],intn)操作结果：返回快速排序所用时间。TSelectsort(inta[])操作结果：返回选择排序所用时间。TshellInsert(inta[],intdk)操作结果：返回希尔排序所用时间。}ADTOrderadlelist数据存储方式为线性数组的形式。定义方式：inta[N]其中N=30000数组大小为30000.既能满足要求且方便使用。软件结构设计：功能模块有：直接插入排序，选择排序，快速排序，冒泡排序，堆排序，希尔排序，效率比较，显示随机数，退出操作九个模块。各模块之间是独立的，都是按钮操作触发。插入排序函数：在doubleTInsertSort(inta[])内调用voidInsertSort(b)函数和Disp(inta[])函数。选择排序：先调用doubleTSelectSort(inta[]),再调用voidSelectSort(inta[])和Disp(inta[])函数。快速排序：先调用doubleTquicksort(inta[],intn),再调用voidquicksort(inta[],intn)和Disp(inta[]);冒泡排序