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

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

1、华北科技学院课程设计说明书班级：计科B10-2姓名：XXX学号XX设计题目:综合排序设计时间:2012生6刀25至2012年7丿寸6号指导教师王晓菊评语:一、设计题目与要求排序综合利用随机函数产生N个随机整数（20000以上），对这些数进行多种方法进行排序。要求：1）至少采用三种方法实现上述问题求解（提示，可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序）。并把排序后的结果保存在不同的文件屮。2）统计毎一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的方法。二、概要设计1・

2、功能需求分析综合排序排序对象为：利用说nd（）函数产生随机数实现以下功能：1、进行简单插入排序2、进行折半插入排序3、进行快速排序4、进行直接选择排序5、进行堆排序二、总体设计综合排序功能结构图根据程序的功能，该程序的结构图如下:1简单插入排序2折半插入排序快速排序4直接选择排序5堆排序其他数字退出模块简介依据程序的功能模块的划分，各模块定义如下：1、简单插入排序模块名：voidInscrtSort(SqList*L)模块描述:简单插入排序，利用循环语句，从第二个数开始，将每一个数与之前的所有数进行比较，如果比前面的数小，就与前一位数

3、交换位置，直到遇到前一位数比口己小，才停止移动，结束本次循环，进行下一次循环，进行下一位数的比较排序，如此循环直到最后一个数比较结束，完成所冇排序数的比较，实现排序。2、折半插入排序模块名：voidBlnsertSort(SqList*L)模块描述：折半插入排序，同简单插入排序差不多，也是利用循环语句，从第二个数字开始比较，不同的是，这半查找是以第一位数为最小位，以待比较数而一位为最高位，将带比较数与最小为与最高位中间的那一位进行比较，如果待比较数犬于等于这一位数，则中间位变为新的最小位，如果待比较数小于中间位数，则屮间位变为最大位，

4、如此循环，直到最小位大于最高位，将最高位后面的每一个数后移，将待比较数放入最高位后面的一位，结束本次循环，进行下一次循环，直到所冇数完成排序，跳出该函数，实现排序。3、快速排序模块名：voidQuicksort(SqList^L)模块描述：快速排序，与之前的两种排序有所区别，采用了递归的思想，附设两个指针low和high,他们的初值分别为1和最后位，设枢纽记录的关键字为pivotkey,则首先从high位所指位置起向前搜索找到第一个关键字小于pivotkey的记录和枢纽记录互相交换，然后从low所指位置起向后搜索，找到第一个关键字人于

5、pivotkey的记录和枢纽记录互相交换，重复这两步直到low二high为止。然后形成以pivotkey为划分的两部分，然后两部分分别进行上述操作，如此继续，直到毎一个划分比较完成，实现排序，该函数结束。4、直接选择排序模块名：voidSclcctSort(SqList*L)模块描述：直接选择排序，相对比较简单，从第一位数开始，用第一位和后面的数进行比较，当所比较的数比这位数小时，再用较小的数继续与后面的数进行比较，直到最后比较出一个最小的数，将这个数与第一位数进行交换，然后第二位数进行同样的运算，直到最后一位数完成这种运算，排序完成

6、。5、堆排序模块名：voidIlcapSort(IIcapTypc*11)模块描述：门个元索的序列，当且仅当满足下列关系时(ki<=k2iki<=k2i+l或ki>二k2iki>二k2i+l)，称之为堆。若将和此函数对应的一维数组看成是一个完全二叉树，则堆得含义表明，完全二叉树中所有非终端节点的值不大于(不小于)其左右孩子的值。由此，则堆顶元素必为序列屮n个元素的最小值(最大值)。输出堆顶的最小值Z后，使得剩下的「1个元素又重新建成一个堆，则得到n个元素中的次小值，如此反复执行，完成排序。三、详细设计1、该程序的主程序：利用mnd()

7、函数产生随机数，然后进入主菜单按照提示进行相关操作输入需要产生領机教的个数/输入所产生随/机数的品大俏2、进入主菜单后根据需要选择述需方式，当选择简单插入排序的时候，流程图如下：3、进入主菜单后根据需耍选择述需方式，当选择折半插入排序的时候，流程图如下：4、进入主菜单后根据需耍选择述需方式，当选择快速排序的时候，流程图如下：5、进入主菜单后根据需要选择还需方式，当选择直接选择排序的时候，流程图如下：6、进入主菜单后根据需要选择述需方式，当选择堆排序的时候，流程图如下:请输入需要产生随机数的最大值=200001、初始界面，输入产生随机数

8、的个数和最值，并完成初始设置后进入菜单MENU入入序择请选择一个內部排序的方法1234按5选择操作■按其他犍退岀程序搜狗拼音2、进行一次排序后继续进行下一次排序的选择界面:3、进行简单插入排序的执行结果:c*I:®程