1、 数数 据据 结结 构构 课课 程程 设设 计计 说说 明明 书书 学生姓名学生姓名: 学学 号：号： 学生姓名学生姓名: 学学 号：号： 学生姓名学生姓名: 学学 号：号： 学生姓名学生姓名: 学学 号：号： 学生姓名学生姓名: 学学 号：号： 学学 院院: 软件学院软件学院 专专 业业: 软件工程 题题 目目: 排序算法实现与演示系统 成成绩绩 指 导 教指 导 教 师师 2012 年 1 月 8 日 1 1 设计目的设计目的 本系统是为了实现和比较各种不同排序方法的不同复杂度,而建立的,从不同的角度比较 各算法的优劣,从而使使用者能对个排序方法有更清晰的了解. 2. 设设计内容和要求计内
2、容和要求 本次设计的内容主要有实现各种排序算法以及比较各种算法。 要求主要是要执行对一种数 据类型的序列进行所有排序方法的排序计算，并返回序列及各算法的排序指标。 3 3本设计所采用的数据结构本设计所采用的数据结构 本次设计主要采用的数据结构有结构体定义， 直接排序， 选择排序， 归并排序， 快速排序， 冒泡排序，希尔排序，堆排序等。 4 4功能模块详细设计功能模块详细设计 4.4.1 1 详细设计详细设计思想思想 本次设计分主题设计和模块设计两部分。 主体设计方面，本系统的主要数据类型为含有一个关键字的结构体类型，命名为 datatype；设置两个全局变量数组，cn 和 mn，分别用于记录每
3、种排序方法中的各排序元素 的比较次数和移动次数（关键字交换以 3 次计）的总和。 模块设计方面， 本系统大致可分为排序模块部分和运行模块部分。 排序模块部分分为归并 排序模块，快速排序模块，冒泡排序模块，选择排序模块，直接排序模块，希尔排序模块， 堆排序模块；运行模块部分分为主函数，自行输入模块，随机模块，输出模块。 以下是各排序算法的核心设计思想： 冒泡排序 相邻两元素进行比较，如有需要则进行交换，每完成一次循环就将最大元素 排在最后（如从小到大排序） ，下一次循环是将其他的数进行类似操作 快速排序 使用分治法（Divide and conquer）策略来把一个序列（list）分为两个子序列
4、 （sub-lists） ，从数列中挑出一个元素，称为 “基准“，重新排序数列，所有元 素比基准值小的摆放在基准前面， 所有元素比基准值大的摆在基准的后面 （相 同的数可以到任一边） ，递归地（recursive）把小于基准值元素的子数列和大 于基准值元素的子序列排序 插入排序 将一个记录插入到已排好序的有序表（有可能是空表）中,从而得到一个新的 记录数增 1 的有序表 选择排序 每一趟从待排序的数据元素中选出最小（或最大）的一个元素， 顺序放在已 排好序的数列的最后，直到全部待排序的数据元素排完 希尔排序 将待排序的元素分为多个子序列，使得每个子序列的元素个数相对较少，对 各个子序列分别进行
5、直接插入排序，待整个待排序序列“基本有序”后，再 对所有元素进行一次直接插入 2 堆排序 堆排序(HeapSort)是一树形选择排序。堆排序的特点是：在排序过程中，将 Rln看成是一棵完全二叉树的顺序存储结构， 利用完全二叉树中双亲结点和 孩子结点之间的内在关系(参见二叉树的顺序存储结构)， 在当前无序区中选择 关键字最大(或最小)的记录 归并排序 归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序 表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有 序子序列合并为整体有序序列。 运行模块个算法如下： 主函数 首先选择一种生成原始数列的方法，然后经过选择进入
6、相应的界面，将数 据排序后输出，并显示出排序比较结果。 手动输入函数 依次输入数据，记录在一个已定义的寄存器中，待排序时使用。排序时将 各排序模块函数调用，排序得出结果。 自动输入函数 调用已有的库函数产生所输入的个数的数列，然后调用已有排序函数，得 到排序后数列，然后输出。 4.4.2 2 核心核心代码代码 #include #include #include #define MAXNUM 100 typedef struct int key; datatype; datatype RMAXNUM;/*定义类型*/ int cnMAXNUM,mnMAXNUM; void D_InsertSort(datatype R , int n)/*直接排序*/ int i,j; extern int cnMAXNUM,mnMAXNUM; for(i=2; i0; i- ) HeapAdjust(R, i, n); for(i=n; i1; i-) R0=R1; R1=Ri; Ri=R0; mn
