归并排序算法论文

1、 归并排序算法解决排序问题目录 TOC o 1-5 h z HYPERLINK l bookmark2 o Current Document 1 引言 2 HYPERLINK l bookmark4 o Current Document 归并排序的基本思想 2 HYPERLINK l bookmark6 o Current Document 归并排序算法不同的方式 3 HYPERLINK l bookmark8 o Current Document 归并排序基本算法 3 HYPERLINK l bookmark10 o Current Document 实现过程 3 HYPERLINK l b

2、ookmark24 o Current Document 性能分析： 4 HYPERLINK l bookmark26 o Current Document 递归二路归并排序 5 HYPERLINK l bookmark28 o Current Document 算法过程 5性能分析： 6 HYPERLINK l bookmark32 o Current Document 归并排序算法的改进算法 7 HYPERLINK l bookmark34 o Current Document 引理 7 HYPERLINK l bookmark36 o Current Document 应用例子 7 HY

3、PERLINK l bookmark38 o Current Document 时间复杂性的分析 8 HYPERLINK l bookmark40 o Current Document 总结 9 HYPERLINK l bookmark42 o Current Document 参考文献 91 引言从归并排序的概念上进行分析，该算法的思想比 较容易理解，并且也能够直观的感知其实 质是利用存储空间的归并。在实现的过程中，可以有多种方法， 画出归并过程示意图后， 随即可以得出其算法的代码。 但是我们在利用递归思想实现归并排序的教学程中， 一定要让 学生分清是用递归还是用回归进行的归并， 画出图形区

4、分这两种不同的归并过程。 通过这一 环节，我们不但能够理解稳定的归并排序， 而且还让学生认清递归和回归是解决这一问题两 种不同的操作过程。2.归并排序的基本思想归并排序主要是二路归并排序，它的基本思想是：设 n 个 数据，初始时把他们看成 n 个长度为 l 的有序子数组，然后从 第个子数组开始，把相邻的子数组两两归并，得 到 n 2 个长 度为 2 的新的有序子数组 （当 n 为奇数是最后个新的有序子 数组长度 为 1） ；对这些新的有序子数组再两两归并；如此重复，直到得到个长度为 n 的有序数组为止”。 归并排序有两种实现方法： 自顶向下和自底向上， 前者定 义是自底向上，3.归并排序算法不

5、同的方式1.归并排序基本算法1.实现过程当初次理解归并概念的时候，我们可以列举下列 一组数据的归并过程。 例如： 70 83 100 65 10 32 7 65 9第一次：【70 83】【65 100】【10 32】【7 65】【9】 第二次：【65 70 83 100 】【 7 10 32 65】【9】 第三次：【7 10 32 65 65 70 83 100 】【9】 第四次：【7 9 10 32 65 65 70 83 100 】 具体程序代码如下：函数： void merge(int e ， int n) 形参说明： e 是已知待排序的数组， n 是数组中元素的个数，下标从 0 开始。

6、 void merge(int e ， int n) int +p=(int+)malloc(Sizeof(int)+n) ； * 开辟一块实现交替归并空间 * int len=l，f=0； *len 为归并单元宽度， f 是一个标识，实现交替归并 * while(1enn) *当归并单元达到或者超过序列长度时，归并结束* if(f=0)merge pass(e ， P， n，len) ； *交替进行归并 * else merge pass(p， e，n，fen);len*=2 ； *扩大归并单元宽度 * f=lf；if(f) *将最终结果存放的指定数 据域中 * for(f=0;fn ； f

7、+)ef=pf ； free(p);Void merge_pass(int e ，int a ， int n，intlen)int f _S，s_end； *f_ s 存放即将归并的第一个单元起始下标 *f _s=0； *S_end 存放即将归并的第二个单元末下标 * while(f_s+ len=n)s end=n 一 1; * 确定真正末下 标位置 *merg_step(e ， a， f_s ， f_s+len-1， s_end)； *实现将两个单元合并 * f_s=S_end+l;if(f_sn) *没有归并的部分复制过去，保证交替归并的正确进行 * for( ； f_sn； f_s+)

8、af_s=ef S；void merge step(int e ，int a ， int s， int m，int n) * 实现将两部分单元归并， m 为分界点下标， 即为第一单元的末下标 * int i， J， k； k=i=s； J=m+1； while(i=m j=n) if(ei=ej ak+=ei+;else ak+=ej+; while(i=m) ak+=ei+; while(j=n) ak+=ej+;2.性能分析：利用最基本的方法实现归并排序， 我们需要利用三个函数， 在实现的过程中， 程序的可读较 高。但是在程序执行的过程中， 函数之间需要频繁的进行嵌套调用， 数据的交替归并

9、也显得 比较麻烦，所以在正确的实现归并算法的基础上，我们引入了递归序列的方法。2.递归二路归并排序1.算法过程利用递归的思想可以掩盖上一方法的频繁嵌套调用，而利用递归的真正目的还可以解决上一方法中数据的交替归并，其方法是它将数组分解成两部分a1，?，am和am+1，?，ar来排序数组a l，?，ar。这两个子数组部分独立排序（通过递归调用），而且将 生成的有序予文件归并得到最后的所有文件。进而可以得到一个原形化的分治递归程序。在分解过程中我们可以参照下面的数据分解图。例如：一组数据为：70、83、100、65、10、32、7、65、9共9个元素，由元素的个数我们可以画出二分递归图形。令函数内部

10、第一次递归调用左半部分，可以得出归并的过程:70 83 100 65 10 32 7 65 970 83 100 65 10 32 7 65 970 83 100 10 6532 7 65 910 65 70 83 100 32 7 65 910 65 70 83 100 7 32 65 910 65 70 83 100 7 32 9 6510 65 70 83 100 7 9 32 657 9 10 32 65 65 70 83 100Void merge(i nt sr,i nt tr,i nt I,i nt m,i nt n)Int j2=m+1,j1=l,k=l;if(srj1=srj

11、2)trk+=stj1+；else trk+=srj2+；while(j1=m)trk+=srjl+；while(j2=n)trk+=srJ2+；for(k=i ； k=n ； k+)srk=trk;)Void msort(int sr , int tr , int S, int t)t int m ;if(s=t)trs=srS;else (m=(s+t) / 2;msort(sr, tr, s, m);msort（sr ， tr， m+l， t） ； merge（sr ，tr ， s， m，t）；）)2.性能分析： 由于本次二路归并排序算法是通过递归划分有序段的，且递归的深度恰好与 n 个

12、结点的完 全二叉树的深度相同，每个有序段的长度不超过n， 所以两个有序段的合并算法时间数量级不会超过 0(n)。因此，对n个记录进行归并排序的时间性能T(n)-0(nl092n)。空间上，需要两个与待排序记录序 列空间等长的辅助空间及递归时深度为 l092n 的栈空 间，因此， 总的空间需求为 S(n)=0(n+l092n)。对于每个递归程序都有一个对应的非递归程序， 虽然等价， 但它可以按不同的顺序来执 行。作为分治算法设计思想的一个原型， 归并排序的递归与非递归的区别值得我们详细加以 研究。请看递归算法完成的归并序列。 如下所示， 一个共有 9 个元素的序列通过如下归并序列 进行排序： (

13、n+m 表示 n 个元素与 m 个元素进行归并 )1+1 2+1 1+1 3+2 1+1 1+1 2+2 5+4 归并的顺序由算法的递归结构决定。但如果采用 的是非递归的方法，各子序列被独立 处理，归并则可 以按不同的结合序列来完成。如下显示了第一次的非 递归策略进行排序， 其中的归并序列为：l+1 1+1 1+1 1+1 2+2 2+2 4+4 8+1 在这两种情况下，递归的结合形式是：4个1+1， 1个 2+1， 1个 2+2， 1个 3+2， 1个5+4，而非递归的结合形式是： 4个 1+1， 2个 2+2， 1个 4“， 1个 8+1。不但归并的完成顺序不 同，而且归并元素的分配也是不

14、同的。 递归方法的分配方式是在单方向递归的过程中分配好 归并的次序， 当单个递归结束后， 进 行回归的时候， 开始进行真正的归并， 在归并的过程 中 还要确保右边的归并集合也是有序的， 进而在回归的过程中还要进行右边归并集合的归并操 作，如此不断地进行，最后则达到有序整体。归并排序算法的改进算法1.引理设有p个数据，若用下列方法分组，X ?GI(tl, 2, ? , P)满足：t=1+(x-min)/(max-min)X (p-1).其中，min , max是这P个数的最小值和最大值。 则对任意xX?Gy?G x s。排序的体算法： 设有 n 个数据序列， m=n/2 前 m 个数据的最小值为

15、 min ， 最大 值为 max。若rain=max，则执行 。用引理方法分组。若组GI中的元素多于一个，则需要用递归再次调用本排序算法。对于后m=n-n/2个数据，令其最小值为 min，最大值为 max，若min=max则执。用下列方法对该 m个数据分组，x Go,满足：1=【n, 2】+l+(x min)/(max-min)。若 Gi 中数据元素多于个,则利用递归继续排序。应用两路归并算法,将已有序列的前 n/2 个与 n-n/2 个数据归并成个长度为 n 的完整排序序列。该算法对“散列型”数据序列排序较优,而对“密集型” 数列排序要增加一些存储空 间。2.应用例子数列 X=3 5,70,

16、43 , 50, 10040604。 8,80, 1o 利用该算法 排序过程为n=10, n/2=5，在前五个数据中min-3 5,max=10.0分组 Gl=35, 43, 50, G2, G3=70, G4=, G5=100。递归：n=3，在n/2=1的第一个数据中 min=3 . 5, max=3. 5, 而单个 G2=3. 5 有序。而后 3-1=2 个数据分组 G2=(43, 50)中 min=43, max=50 又进行递归： 2/2=1 得G2=4. 3, G3=5. 0.归并G1, G2, G3后得有序子序列3. 5, 4. 3, 5. 0),因此可得 前五个有 序子序列为 f

17、35, 43, 50,70, 10oJ。n=10 的后五个数据中min=1 0, max=80 递归步骤 (1)和 (2)后得 G110,G2=,G3=4. 0, G4=(4. 8, 6. 0), G5= 8. 0。递归步骤 ：n=2,这两个数据的前一个 数据 min=4. 8, max=4. 8,则这单个数据序列 4. 8有序。这两个数据后个数据的max=min=6. 0单个6. 0)有序,归并后得有序子序列 (1. 0, 4. 0, 4. 8, 6. 0, 8. 0)。最后得两个长度为 5的子序列归并为长度为 10的有序序列,此为排序的结果。时间复杂性的分析命题： n 个数据归并排序改进算

18、法的时间复杂性为T(n)=O(nlogn)证明：设n个关键字排序的算法所需时间为M(n),最坏情 况下，n , 2个数据全部被分配到同一组中，而求出 In/21 个数据 的最大值和最小值所需的时间是 n 的线性函数， 而两路归并排 序所需的时间也是 n 的线性函数，因此有：M(n)=cn+2M(n/2)将n个数据项排序所需的时T(n)展开成：T(n) 1 T(n)=Co n=l其中C1和c0均为某个正常数，c,n表示递归划jl【d-3第一步所需要的时间，因为M(r1)时间是线性的，所以上述公式可近似地表示为：T(n)wcn+2T(11 , 2) n1T(n)=co n=1 其中 C 也是某个正常数，由此可得递归方程的解为：T(n)=cnlogn+O(n) 所以在最坏的情况下，该算法的时间复杂度为T(n)=O(nlogn)4.总结总之，以上几种归并排序的实现形式，是两个基 本的归并排序算法，均以归并两个有 序序列为一个有 序序列的运算为基础。 这两个算法紧密相关， 而且实 际上， 当排序元素个 数为 2 的幂时， 它们执行着相 同的归并集合， 但它们却并不相等， 因为归并集合 的结合顺 序是不一样