1、 1 / 11 前前 言言 1.1 排序的重要性 生活中，无时不刻不充满这排序，比如：班级同学的成绩排名问题，公司产值高低 的问题等等，解决这些问题的过程中，都涉及到了一个数据结构的构造思想过程。数据 结构中的排序，也有很多种，如：插入排序、交换排序、选择排序等等，此时我们就要 注意选择具有优解的算法，将一个数据元素（或记录）的任意序列，重新排列成一个有 序的排列，便于我们查找。 假设含有 n 个记录的序列为R1,R2,Rn,其相应的关键字序列为K1,K2,Kn需确 定 1，2n 的一种排序 P1,P2Pn,使其相应的关键字满足如下的非递减的关系：Kp1 Kp2Kpn,即按关键字Rp1,Rp2
2、,Rpn有序的排列，这样的一种操作称为排序。 一般情况下，排序又分为内部排序和外部排序。而在内部排序中又含有很多排序方法， 就其全面性能而言，很难提出一种被认为是最好的方法，因为每一种方法都有它的优缺 点，适合在不同的环境下使用。我们学习的排序有:直接插入排序、折半插入排序、希尔 排序、快速排序、基数排序、归并排序等。本次课题研究中，我主要进行了二路归并排 序的研究和学习。 1.2 设计的背景和意义 排序是计算机领域的一类非常重要的问题，计算机在出来数据的过程中，有 25%的 时间花在了排序上，有许多的计算机设备，排序用去计算机处理数据时间的一半以上， 这对于提高计算机的运行速度有一定的影响。
3、此时排序算法的高效率显得尤为重要。 在排序算法汇中，归并排序（Merging sort）是与插入排序、交换排序、选择排序不 同的另一类排序方法。归并的含义是将两个或两个以上的有序表组合成一个新的有序 表。归并排序可分为多路归并排序，两路归并排序，既可用于内排序，也可以用于外排 序。这里仅对内排序的两路归并排序进行讨论。 而我们这里所探究学习的二路归并排序，设计思路更加清晰、明了，程序本身也不 像堆结构那样复杂，同时时间复杂度仅为 0(N)，同时在处理大规模归并排序的时候，排 序速度也明显优于冒泡法等一些排序算法，提高排序算法的效率。 正正 文文 2.1 设计内容 设计一个利用二路归并算法实现的
4、排序算法，针对输入的一组无序的数，利用栈或 者数组机芯存储，然后进行数据的两两分组、比较，构造新的栈或者数组，依次类推， 直到得到一个有序数组或者栈，最后输出有序数据，得到有序数据。 2.2 设计要求 假设初始序列含有 n 个数据（n 是已经确定的数据个数） ，首先把 n 个记录看成 n 2 / 11 个长度为 1 的有序序列，进行两两归并，得到n/2个长度为 2 的有序序列，再两两归并 直到所有记录归并成一个长度为 n 的有序序列为止。 2.3 设计思想 对于任意一组数据，先利用栈或者数组将数据存储起来，其中，我们会用到线性表 的顺序存储和链式存储两种存储方法。然后对存储的数据进行查找和筛选
5、、排序，在出 栈的过程中，同时对所取数据进行分组、排列，再次构造新的存储栈或者数组，依次类 推，直到得到一个有序的数据时，执行出栈命令，输出最后的排序结果。 为了更清晰地说清楚这里的思想，大家来看图 1，我们将本是无序的数组序列 16,7,13,10,9,15,3,2,5,8,12,1,11,4,6,14，通过两两合并排序后，再合并，最终获得了一个 有序的数组。仔细观察它的形状，很像一棵倒置的完全二叉树，利用两两的比较，一次 进行递归排序，最终得到一个从小到大的有序序列。 图 1 2.4 主要模块 主要模块式有四个阶段，依次是：输入一组无序的数列，用数据结构或者链式结构 进行存储，然后进行查找
6、、分组，进行最后的归并排序。 （如图 2 所示） 3 / 11 图 2 2.5 排序设计内容 此次操作要用到顺序结构的存储，顺序表的查找，以及二路归并排序。 2.5.1 顺序表的存储 首先利用顺序存储结构，把所有学生的成绩按每个班，每个学校，每个县，每个市， 用线性表的顺序存储机构分别存储起来。 顺序表的基本操作如下： Initlist( Destroylist( Clearlist( 哨兵； For(i=ST.length; !EQ(ST.elemi.key.key) 从后往前找； Return I; 找不到是 i 为 0； /Search-Sep 2.5.3 归并排序 代码： /* 对顺序表 L 作归并排序 */ void MergeSort(SqList *L) MSort(L-r,L-r,1,L-length); 输 入 一 组 无 序 的 数 据 存 储 查 找 ， 分 组 归 并 排 序 4 / 11 2.6 算法设计 本次设计主要用用到下面的
