数据结构课程设计--排序综合

《数据结构课程设计--排序综合》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、数据结构课程设计题目排序综合张鸣敏学生姓名学号2008012325学院计算机与软件学院专业软件工程指导教师二0一0年06月06题目：综合排序姓名张鸣敏专业软件工程学院计算机与软件学院1．题目解析问题内容：利用随机函数产生N个随机整数（20000以上），对这些数进行多种方法进行排序。要求：1)至少采用两种方法实现上述问题求解（提示，可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序）。并把排序后的结果保存在不同的文件中。2)统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的方法。3)

2、如果采用4种或4种以上的方法者，可适当加分。程序的设计思路与流程题意分析与数据结构分析：1.对于排序算法的数据结构选择本问题为比较多种算法的时间复杂度的方式，对于多种内排序方法进行比较与归类。鉴于常用性，本次课程设计所选用的排序算法为算法基础性的插入排序、选择排序、冒泡排序算法，以及经过算法优化的希尔排序以及快速排序算法。堆排序与归并排序未选用。经过资料查询【1】，所得到的此五种排序算法的算法简要介绍如下：插入排序：将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。是

3、稳定的排序方法。算法示意如下：将n个元素的数列分为已有序和无序两个部分，如下所示：　　{，{a2，a3，a4，…,an}}　　{{a1(1)，a2(1)}，{a3(1)，a4(1)…,an(1)}}　　…　　{{a1(n-1)，a2(n-1)，…},{an(n-1)}}　　每次处理就是将无序数列的第一个元素与有序数列的元素从后往前逐个进行比较，找出插入位置，将该元素插入到有序数列的合适位置中。希尔排序：插入排序的一种改进，把排序区间分成若干小份分别进行插入排序，并不断减少区间长度增量。因此，该方法又称缩小增量排序。算法示意如下：先取一个小于n的整

4、数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2

5、，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。重复以上过程，仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），将小数放前，大数放后，一直比较到最大数前的一对相邻数，将小数放前，大数放后，第二趟结束，在倒数第二个数中得到一个新的最大数。如此下去，直至最终完成排序。冒泡排序是稳定的。时间复杂度为O(n^2)选择排序：每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。　　选择排序是不稳定的排序方法。　　n个记录的文件

6、的直接选择排序可经过n-1趟直接选择排序得到有序结果：　　①初始状态：无序区为R[1..n]，有序区为空。　　②第1趟排序　　在无序区R[1..n]中选出关键字最小的记录R[k]，将它与无序区的第1个记录R[1]交换，使R[1..1]和R[2..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。　　……　　③第i趟排序　　第i趟排序开始时，当前有序区和无序区分别为R[1..i-1]和R(1≤i≤n-1)。该趟排序从当前无序区中选出关键字最小的记录R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R分别变为记录个数增加1

7、个的新有序区和记录个数减少1个的新无序区。这样，n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果。时间复杂度为：O(n^2)快速排序：快速排序是对冒泡排序的一种本质改进.它的基本思想是通过一趟扫描后.使得排序序列的长度能大幅度地减少.在冒泡排序中.一次扫描只能确保最大数值的数移到正确位置.而待排序序列的长度可能只减少1.快速排序通过一趟扫描.就能确保某个数的左边各数都比它小.右边各数都比它大.然后又用同样的方法处理其左右两边的数.直到基准点的左右只有一个元素为止快速排序的程序的时间复杂度为：O(nlog2n)(最好)，O(n^2

8、)（最次）2.大量随机数据生成的函数实现针对本例中所要求的N>20000的随机数生成算法，编辑思想基于VC++中stdlib.h包含的r