合并排序算法论文.docx

合并排序算法研究1（1.河南大学 计算机与信息工程学院，河南 开封 475004）摘要：分治法是一种非常重要的解题方法，其基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同，递归的了解这些子问题，然后将各子问题的解合并得到原问题的解。合并排序算法即是运用分治策略来实现对n个元素进行排序的算法。文章论述的目的是建立在分治法的基础上，采用递归，非递归和自然合并排序三种方法来实现的合并排序算法，同时通过三种方法的时间复杂度和空间复杂度对三种方法的计算过程进行深入的探讨和研究，在仔细分析三种算法的优点和缺点并进行比较之后，最终得出对于所给的n元素数组已排序好序的极端情况，采用自然合并排序方法实现的合并排序算法明显优于非递归和递归方法实现的合并排序算法，因为它的合并过程中所需的合并次数较少时间复杂度最低。关键词：合并排序；递归；分治法；非递归research on merge sort algorithmduan xiao-yu11(college of computer science and information engineering, henan university, kaifeng 475004, china)abstract: the method is a very important problem solving method, the basic idea is to be a problem of size n k is decomposed into smaller sub problems, these problems are independent of each other and with the same problem, recursive understanding of these problems, and then combine their solutions to solve the original the solution of the problem. merge sort algorithm is used to divide and conquer strategy to achieve sort of n element algorithm. this article aims to establish a recursive divide and conquer based on merge sort algorithm, non recursive merge sort and natural three ways to realize the in-depth discussion and research carried out at the same time through the three methods of time and space complexity of the three methods of the calculation process, after careful analysis advantages and disadvantages of these three algorithms were compared, obtained for n elements to the array is sorted by the extreme situation, natural merge sort merge sort algorithm implementation method is obviously better than the merge sort algorithm non recursive and recursive method to realize, because the required in the course of its merger with fewer the minimum time complexity.key words: merge sort；recursion；divide and conquer method；non-recursive0引言分治策略是一种在排序算法中应用最多的方法之一，之前的研究当中都是对合并排序进行递归和非递归的研究但并未对自然合并排序进行详细的研究比较，本文的目的即对三种方法进行探讨并通过时间复杂度和空间复杂度来比较并得出结论。1分治法概述1.1分治法的描述所谓分治法，是指对一个输人规模为n的问题，用某种可行的方法把输人分割成1个子集1ln，从而产生k个规模较小的子问题，解出k个子问题后，再用某种方法把它们组合成原来问题的解，如果子问题还相当大则反复使用分治法，直到最后的子问题分得足够小，不必再进行分割就可以直接得出它们的解。使用分治法时，子问题的类型常常和原来的相同，因而很自然地使用递归过程。1.2分治法的适用条件分而治之是一种解题的方法，其基本思路是：“如果一个大问题比较复杂，就可以将这个问题分解，然后各个击破。”分治从字面上包含了“分”和“治”两层含义，那么如何分，分后又如何“治”就成为我们解决问题的关键之处。通常并不是所有的问题都可以采用分治策略，只有那些能将问题分解成与原问题相似的!意思接近的子问题，并且再合并以后依然符合原问题的意思的这些问题，才能适用分治策略。一般的，能够使用分治算法解决的问题有以下几点特征：（1）此问题在规模上可以缩小到一定的程度就能很容易地解决。一般的问题都能满足这个条件，这是因为一般问题的计算复杂性都是随着问题规模的增大而增大。（2）此问题能够分解成若干个类似的规模较小的问题，也即该问题能够分解成若干个子问题来解决。这是分治策略应用的前提，一般大多数问题都是可以满足的，这个特征充分反映了分治策略中递归思想的应用。（3）若干个分解出的子问题的解能够合并为原问题的解，这一点是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑用贪心法或动态规划法。（4）此问题分解得出的若干子问题必须是相互独立，即分解的子问题相互之间不存在公共的子子问题。这就涉及到分治策略的使用效率，如果各个子问题相互之间是不独立的，有共性部分，则分治法就要做许多重复的工作，公共的子问题被重复地解决，此时虽然可以使用分治算法，但其效率较低，这时反而使用动态规划算法较好。2合并排序算法的描述合并排序是建立在合并操作上的一种有效的排序算法。该算法是采用分治法（divide and conquer）的一个非常典型的应用。合并排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路合并。合并排序也叫归并排序。2.1合并排序递归算法描述合并排序递归算法。假设对应的待排序集合为ai，ai被划分之后对应的两集合分别为ai1和ai2。令集合ai中元素个数记为|ai|。按照合并排序算法思想，该排序过程是一个递归过程，它包括集合划分过程的递归和排好序子集合合并过程的递归。公式如下：fai ，a(i+j)/2-1，a(i+j)/2，a(i+j)/2+1，aj=fai =ai j=ifai +faj=ai ，aj ai 1 （1） 当|ai|=1时，ai不需要再划分，且该集合中元素为已排好序情形。（2） 当|ai|1时，该集合需要进一步划分为ai1和ai2.单从集合划分的角度来看，划分过程存在边界，对应为第1种情形。对于第2种情形为递归模式，它能将问题转化到边界情形。借助形式化的表述方式，合并排序对应的递归定义如上式所示。其中该式中的f函数定义为集合排序后的输出结果，运算符定义为合并操作，合并排序递归边界条件对应为情形，其递归模式对应为j-i1情形。2.2合并排序非递归算法描述合并排序非递归算法。算法mergesort的递归过程只是将待排序集合一分为二，直至待排序集合只剩下一个元素为止，然后不断合并两个排好序的数组段。按此机制，可以首先将数组a中相邻元素两两配对。用合并算法将它们排序，构成n/2组长度为2的排好序的子数组段，然后再将它们排序成长度为4的排好序的子数组段，如此继续下去，直至整个数组排好序。2.3合并排序自然合并排序算法描述合并排序自然排序算法。对于初始给定的数组a，通常存在多个长度大于1的已排好序的子数组段。因此用一次对a的线性扫描就可以找出所有这些排好序的子数组段，然后将相邻的排好序的子数组段两两合并。3合并排序算法的设计与实现2.1合并排序算法设计3.1.1合并排序递归算法设计合并排序递归算法设计过程中需要考虑两个因素:（1）数据源的存储;（2）数据集的排序操作。待排序序列如何存储，这一问题的回答将直接影响到数据集排序操作的具体细节。考虑到数组较链表结构对存储开销代价低这一因素，本文采用数组type b来存储数据源。由合并排序递归求解过程可知，数据源涉及到划分后两个子集合的排序和排好序的两子集合合并操作，且这一过程具有递归特性。受面向对象程序设计思想的启发，由于类具有封装性特点，因此，本文利用mergesort类封装合并排序数据源及上两种形式的操作。其中，merge:(int start，int end)抽象对type aleft，type aright这right-left+1个元素的排序操作。mergesort：merge(int a，left，i)抽象对子集 type aleft，type ai和子集合 type ai+1，type afight的合并操作。其递归过程如图1，图2所示。图1 待排序列拆分的过程图2 待排序列合并的过程3.1.2合并排序非递归算法设计合并排序非递归算法设计过程中也需要考虑两个因素:（1）数据源的存储;（2）数据集的排序操作。本文采用数组type b来存储数据源。由合并排序非递归求解过程可知，数据源涉及到划分后两个子集合的排序和排好序的两子集合合并操作，因此，本文利用mergesort类封装合并排序数据源及上两种形式的操作。其中，mergepass:(int s，int n)抽象对type as，type an这i个元素的排序操作。merge(int l，int m，int r)抽象对子集 type ai+s-1，type ai+2*s-1和子集合 type ai+s-1，type an-1的合并操作。其递归过程如图3所示。图3 合并排序的非递归实现过程3.1.3合并排序自然排序算法设计对于初始给定的数组a，通常存在多个长度大于1的已排好序的子数组段。因此用一次对a的线性扫描就可以找出所有这些排好序的子数组段，然后将相邻的排好序的子数组段两两合并了例：若数组a中元素为4,8,3,7,1,5,6,2，则自然排好序的子数组段有4,8，3,7，1,5,6，2，经一次合并后得到2个合并后的子数组段3,4,7,8和1,2,5,6，继续合并相邻排好序的子数组段，直至整个数组已排好序，最终结果1,2,3,4,5,6,7,8。3.2合并排序算法实现3.2.1合并排序递归算法实现主要代码如下：将待排序集合一分为二，直至待排序集合只剩下一个元素为止，然后不断合并两个排好序的数组段templatevoid mergesort(type a,int left,int right) if(leftright)/控制待排序数组中至少有两个元素int i=(left+right)/2;/取数组中点，将数组尽量均等划分mergesort(a,left,i);/将左半段进行递归排序mergesort(a,i+1,right);/将右半段进行递归排序merge(a,b,left,i,right);/合并到数组bcopy(a,b,left,right);/复制到数组 3.2.2合并排序非递归算法实现主要代码如下：template /合并大小为s的相邻子数组void mergepass(type x,type y,int s,int n)int i = 0;while(i=n-2*s)/合并大小为s的相邻两段子数组merge(x,y,i,i+s-1,i+2*s-1);i = i + 2*s;/剩下的元素个数少于2sif(i+sn)merge(x,y,i,i+s-1,n-1);elsefor(int j=i; j=n-1; j+)yj=xj;template void mergesort(type a,int n)type *b = new typen;int s = 1;while(sn)mergepass(a,b,s,n);/合并到数组bs += s;mergepass(b,a,s,n);/合并到数组as += s;template void merge(type a,type b,int left,int mid,int right)int i=left;int j=mid+1;int k=left;hile(i=mid & j=right)if(aimid)for(int z=j;z=right;z+)bk+=az;elsefor(int z=i;z=mid;z+)bk+=az;3.2.3合并排序自然排序算法设计主要代码如下：templatevoid mergesort(type a,int n)type *b=new type n;int snum=mergepass(a,n); /snum = 有序子串的个数+1while(snum!=2)for(int i=0;isnum;i+=2)merge(a,b,sli,sli+1-1,sli+2-1); /对snum个子串进行两两合并snum=mergepass(a,n); /求出经上次合并后的数组中有序子串的个数 /得到每个有序子串的起始位置 将其放入数组sl中 函数返回值为有序子串的个数 templateint mergepass(type x,int n)int k=0;int begin=x0;slk+=0; /第一个有序子串的起始位置为0or(int i=1;ixi)slk+=i；begin=xi;slk+=n;return k;4合并排序算法分析4.1合并排序递归算法分析算法merge合并两个排好序的数组段到一个新的数组b中，然后有copy将合并后的数组段再复制回数组a中。merge和copy显然可在o(n)时间内完成，因此合并排序算法对n个元素进行排序，在最坏情况下所需的计算时间t（n）满足：tn=o1 n1 2tn/2+on n1 解此递归方程可得t（n）=o(nlogn)。由于排序问题的计算时间下界为（nlogn），故合并排序算法是一个渐进最优算法。空间复杂度o(n+logn)。4.2合并排序非递归算法分析非递归的合并排序，省略了中间的栈空间，直接申请一段o(n)的地址空间即可，因此空间复杂度为o(n