排序实验报告

1 / 16 排序实验报告 数据结构 课程设计报告 专 业 计算机科学与技术 班 级姓 名学 号指导教师 起止时间 课程设计：排序综合 一、任务描述 排序综合 任务：利用随机函数产生 n 个随机整数，对这些数进行多种方法进行排序。 要求： 至少采用三种方法实现上述问题求解。并把排序后的结果保存在不同的文件中。 统计每一种排序方法的性能，找出其中两种较快的方法。 二、问题分析 1、功能分析 分析设计课题的要求，要求编程实现以下功能： 排序表的建立 即创建顺序表； 顺序表的排序 即直接插入排序、希尔排序、起泡排序、快速排序、简单选择排序操作； 统计每一种排序方法的性能 即测试上机运行程序所花费的时间； 2、数据对象分析 2 / 16 数据信息：随机整数 数据数量可以预先确定 三、数据结构设计 使用顺序表实现，有关定义如下： typedef int Status; typedef int KeyType ; /设排序码为整型量 typedef int InfoType; typedef struct /定义被排序记录结构类型 KeyTypekey ; /排序码 I nfoType otherinfo;/其它数据项 RedType ; typedef struct RedType * r;/存储带排序记录的顺序表 /r0作哨兵或缓冲区 int length ; /顺序表的长度 SqList ; /定义顺序表类型 四、功能设计 主控菜单设计 为实现通各种排序的功能，首先设计一个含有多个菜单项的主控菜单程序，然后再为这些菜单项配上相应的功能。 程序运行后，给出 6 个菜单项的内容和输入提示，3 / 16 如下： 1. 直接插入排序 2. 希尔排序 3. 起泡排序 4. 快速排序 5. 简单选择排序 0. 退出系统 程序模块结构 由课题要求可将程序划分为以下几个模块： ? 主控菜单项选择函数 menu ? 创建排序表函数 InitList_Sq ? 对顺序表 L 进行直接插入排序函数 Insertsort ? 希尔排序函数 ShellSort; ? 起泡排序函数 Bubble_sort ? 快速排序函数 QSort ? 简单选择排序函数 SelectSort 函数调用关系 程序的主要结构如下图所示。 其中 main 是主函数，它进行菜单驱动，根据选择项05调用相应的函数。 main函数使用 for循环实现重复选择。其循环结构如下： for 4 / 16 long start,end; switch) case 1:printf;start=clock;Insertsort;end=clock;printf;fp=fopen; if/打开文件失败 printf; exit;forfprintf; break; case 2: printf; start=clock; ShellSort; end=clock; printf; fp=fopen; if/打开文件失败 printf; exit; for fprintf; fclose; break; case 3: printf; 5 / 16 start=clock; Bubble_sort; end=clock; printf; fp=fopen; if/打开文件失败 printf; exit; for fprintf; fclose; break; case 4: printf; start=clock; QSort ; end=clock; printf; fp=fopen; if/打开文件失败 6 / 16 printf; for fprintf; fclose; break; case 5: printf; start=clock; SelectSort; end=clock; printf; fp=fopen; if/打开文件失败 printf; exit; for fprintf; fclose; 7 / 16 break; case 0: printf; return ; 文件结构 1、：顺序表相关的定义与函数声明 2、：顺序表排序运算的实现 3、：主菜单函数的声明 4、：主菜单函数的实现 5、：主函数 各函数的算法 设计 1、 InitList_Sq 算法原理：数组指针 r 指示线性表的基址， length指示线性表的当前长度，将随机生成的数赋给线性表，并生成相应文件。 流程图： 深 圳 大 学 实 验 报 告 课程名称： 学院： 报告人 8 / 16 实验时间： 实验报告提交时间： 教务部制 【一】需求分析 课程题目是排序算法的实现，课程设计一共要设计八种排序算法。这八种算法共包括：堆排序，归并排序，希尔排序，冒泡排序， 快速排序，基数排序，折半插入排序，直接插入排序。 为了运行时的方便，将八种排序方法进行编号，其中 1 为堆排序， 2为归并排序， 3为希尔排序， 4 为冒泡排序，5 为快速排序， 6为基数排序， 7 为折半插入排序 8为直接插入排序。 【二】概要设计 1.堆排序 算法思想：堆排序只需要一个记录大小的辅助空间，每个待排序的记录仅占有一个存储空间。将序列所存储的元素 AN看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的元素均不大于其左右孩子结点的元素。算法的平均时间复杂度为 O。 程序实现及核心代码的注释： for 9 / 16 if) j+; if break; sui=suj; i=j; sui=temp; void dpx/堆排序 int i,temp; cout output; for head; for temp=sui; sui=su0; su0=temp; 10 / 16 head; cout output; 2.归并排序 算法思想：先将相邻的个数为 1 的每两组数据进行排序合并；然后对上次归并所得到的大小 为 2的组进行相邻归并；如此反复，直到最后并成一组，即排好序的一组数据。 程序实现及核心代码的注释： int is21000; void bin int i=low,j=mid+1,k=low; while if / 此处为排序顺序的关键，用小于表示从小到大排序 is2k+=sui+; else is2k+=suj+; while is2k+=sui+; while is2k+=suj+; 11 / 16 for / 写回原数组 sui=is2i; void g if int mid=/2; g; g; bin; 3.希尔排序 算法思想：先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基 本有序”时，再对全体记录进行一次直接插入排序。其中，子序列的构成 不是简单的“逐段分割”，而是将分隔某个“增量”的记录组成一个子序列。 程序实现及核心代码的注释： while 12 / 16 m/=2; if for if temp=sui; for; j-=m) suj+m=suj; suj+m=temp; 4.冒泡排序 算法思想： 1、先将一组未排序的数组的最后一个数与倒数第二个数进行比较，并将较小的数放于两个数中较前的位置，然后将比较后的较小的数与倒数第三个进行比较，依次比较到第一个数，即可得到第一个数是所有数中最小的数； 2、然后再将数组的最后一个数与倒数第二个数进行比较，并将较小的数放于两个数中较前的位置，依次比较13 / 16 到第二个数， 3、如此循环到只剩最后两个比较，即得到排好序的一组数。 程序实现及核心代码的注释： for flag=true; for if temp=suj; suj=suj+1; suj+1=temp; flag=false; break; cout int K; int find 14 / 16 int temp; bool flag=true; temp=sui; while if while j-; if break; if break; sui=suj;