合并排序算法论文

合并排序算法研究1（1.河南大学计算机与信息工程学院，河南开封475004）摘要：分治法是一种非常重要的解题方法，其基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题互相独立且与原问题相同，递归的了解这些子问题，然后将各子问题的解合并得到原问题的解。合并排序算法即是运用分治策略来实现对N个元素进行排序的算法。文章论述的目的是建立在分治法的基础上，采用递归，非递归和自然合并排序三种方法来实现的合并排序算法，同时通过三种方法的时间复杂度和空间复杂度对三种方法的计算过程进行深入的探讨和研究，在仔细分析三种算法的优点和缺点并进行比较之后，最终得出对于所给的n元素数组已排序好序的极端情况，采用自然合并排序方法实现的合并排序算法明显优于非递归和递归方法实现的合并排序算法，因为它的合并过程中所需的合并次数较少时间复杂度最低。关键词：合并排序；递归；分治法；非递归ResearchonmergesortalgorithmDUANXiao-yu11(CollegeofComputerScienceandInformationEngineering,HenanUniversity,Kaifeng475004,China)Abstract:Themethodisaveryimportantproblemsolvingmethod,thebasicideaistobeaproblemofsizeNKisdecomposedintosmallersubproblems,theseproblemsareindependentofeachotherandwiththesameproblem,recursiveunderstandingoftheseproblems,andthencombinetheirsolutionstosolvetheoriginalthesolutionoftheproblem.MergesortalgorithmisusedtodivideandconquerstrategytoachievesortofNelementalgorithm.Thisarticleaimstoestablisharecursivedivideandconquerbasedonmergesortalgorithm,nonrecursivemergesortandnaturalthreewaystorealizethein-depthdiscussionandresearchcarriedoutatthesametimethroughthethreemethodsoftimeandspacecomplexityofthethreemethodsofthecalculationprocess,aftercarefulanalysisadvantagesanddisadvantagesofthesethreealgorithmswerecompared,obtainedfornelementstothearrayissortedbytheextremesituation,naturalmergesortmergesortalgorithmimplementationmethodisobviouslybetterthanthemergesortalgorithmnonrecursiveandrecursivemethodtorealize,becausetherequiredinthecourseofitsmergerwithfewertheminimumtimecomplexity.Keywords:mergesort；Recursion；Divideandconquermethod；non-recursive0引言分治策略是一种在排序算法中应用最多的方法之一，之前的研究当中都是对合并排序进行递归和非递归的研究但并未对自然合并排序进行详细的研究比较，本文的目的即对三种方法进行探讨并通过时间复杂度和空间复杂度来比较并得出结论。1分治法概述1.1分治法的描述所谓分治法，是指对一个输人规模为n的问题，用某种可行的方法把输人分割成1个子集(1L≤n)，从而产生k个规模较小的子问题，解出k个子问题后，再用某种方法把它们组合成原来问题的解，如果子问题还相当大则反复使用分治法，直到最后的子问题分得足够小，不必再进行分割就可以直接得出它们的解。使用分治法时，子问题的类型常常和原来的相同，因而很自然地使用递归过程。1.2分治法的适用条件分而治之是一种解题的方法，其基本思路是：“如果一个大问题比较复杂，就可以将这个问题分解，然后各个击破。”分治从字面上包含了“分”和“治”两层含义，那么如何分，分后又如何“治”就成为我们解决问题的关键之处。通常并不是所有的问题都可以采用分治策略，只有那些能将问题分解成与原问题相似的!意思接近的子问题，并且再合并以后依然符合原问题的意思的这些问题，才能适用分治策略。一般的，能够使用分治算法解决的问题有以下几点特征：（1）此问题在规模上可以缩小到一定的程度就能很容易地解决。一般的问题都能满足这个条件，这是因为一般问题的计算复杂性都是随着问题规模的增大而增大。（2）此问题能够分解成若干个类似的规模较小的问题，也即该问题能够分解成若干个子问题来解决。这是分治策略应用的前提，一般大多数问题都是可以满足的，这个特征充分反映了分治策略中递归思想的应用。（3）若干个分解出的子问题的解能够合并为原问题的解，这一点是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑用贪心法或动态规划法。（4）此问题分解得出的若干子问题必须是相互独立，即分解的子问题相互之间不存在公共的子子问题。这就涉及到分治策略的使用效率，如果各个子问题相互之间是不独立的，有共性部分，则分治法就要做许多重复的工作，公共的子问题被重复地解决，此时虽然可以使用分治算法，但其效率较低，这时反而使用动态规划算法较好。2合并排序算法的描述合并排序是建立在合并操作上的一种有效的排序算法。该算法是采用分治法（DivideandConquer）的一个非常典型的应用。合并排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路合并。合并排序也叫归并排序。2.1合并排序递归算法描述合并排序递归算法。假设对应的待排序集合为𝐴𝑖，𝐴𝑖被划分之后对应的两集合分别为𝐴𝑖1和𝐴𝑖2。令集合𝐴𝑖中元素个数记为|𝐴𝑖|。按照合并排序算法思想，该排序过程是一个递归过程，它包括集合划分过程的递归和排好序子集合合并过程的递归。公式如下：𝑓({𝑎𝑖，…，𝑎⌊(𝑖+𝑗)/2−1⌋，𝑎⌊(𝑖+𝑗)/2⌋，𝑎⌊(𝑖+𝑗)/2+1⌋，…，𝑎𝑗})={𝑓({𝑎𝑖})={𝑎𝑖}𝑗=𝑖𝑓({𝑎𝑖})+𝑓({𝑎𝑗})={{𝑎𝑖，𝑎𝑗}𝑎𝑖𝑎𝑗{𝑎𝑗，𝑎𝑖}𝑎𝑖≥𝑎𝑗𝑗−𝑖=1𝑓({𝑎𝑖，…，𝑎⌊(𝑖+𝑗)/2⌋−1，𝑎⌊(𝑖+𝑗)/2⌋})+𝑓({𝑎⌊(𝑖+𝑗)/2⌋+1，𝑎⌊(𝑖+𝑗)/2⌋+2…，𝑎𝑗})𝑗−𝑖1（1）当|𝐴𝑖|=1时，𝐴𝑖不需要再划分，且该集合中元素为已排好序情形。（2）当|𝐴𝑖|1时，该集合需要进一步划分为𝐴𝑖1和𝐴𝑖2.单从集合划分的角度来看，划分过程存在边界，对应为第1种情形。对于第2种情形为递归模式，它能将问题转化到边界情形。借助形式化的表述方式，合并排序对应的递归定义如上式所示。其中该式中的𝑓函数定义为集合排序后的输出结果，运算符定义为合并操作，合并排序递归边界条件对应为情形，其递归模式对应为𝑗−𝑖1情形。2.2合并排序非递归算法描述合并排序非递归算法。算法MergeSort的递归过程只是将待排序集合一分为二，直至待排序集合只剩下一个元素为止，然后不断合并两个排好序的数组段。按此机制，可以首先将数组a中相邻元素两两配对。用合并算法将它们排序，构成n/2组长度为2的排好序的子数组段，然后再将它们排序成长度为4的排好序的子数组段，如此继续下去，直至整个数组排好序。2.3合并排序自然合并排序算法描述合并排序自然排序算法。对于初始给定的数组a，通常存在多个长度大于1的已排好序的子数组段。因此用一次对a的线性扫描就可以找出所有这些排好序的子数组段，然后将相邻的排好序的子数组段两两合并。3合并排序算法的设计与实现2.1合并排序算法设计3.1.1合并排序递归算法设计合并排序递归算法设计过程中需要考虑两个因素:（1）数据源的存储;（2）数据集的排序操作。待排序序列如何存储，这一问题的回答将直接影响到数据集排序操作的具体细节。考虑到数组较链表结构对存储开销代价低这一因素，本文采用数组Typeb[]来存储数据源。由合并排序递归求解过程可知，数据源涉及到划分后两个子集合的排序和排好序的两子集合合并操作，且这一过程具有递归特性。受面向对象程序设计思想的启发，由于类具有封装性特点，因此，本文利用MergeSort类封装合并排序数据源及上两种形式的操作。其中，Merge::(intstart，intend)抽象对{Typea[left]，…，Typea[right]这right-left+1个元素的排序操作。MergeSort：：Merge(inta，left，i)抽象对子集{Typea[left]，…，Typea[i]}和子集合{Typea[i+1]，…Typea[fight]}的合并操作。其递归过程如图1，图2所示。图1待排序列拆分的过程图2待排序列合并的过程3.1.2合并排序非递归算法设计合并排序非递归算法设计过程中也需要考虑两个因素:（1）数据源的存储;（2）数据集的排序操作。本文采用数组Typeb[]来存储数据源。由合并排序非递归求解过程可知，数据源涉及到划分后两个子集合的排序和排好序的两子集合合并操作，因此，本文利用MergeSort类封装合并排序数据源及上两种形式的操作。其中，MergePass::(ints，intn)抽象对{Typea[s]，…，Typea[n]这i个元素的排序操作。Merge(intl，intm，intr)抽象对子集{Typea[i+s-1]，…，Typea[i+2*s-1]}和子集合{Typea[i+s-1]，…Typea[n-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合并排序递归算法实现主要代码如下：将待排序集合一分为二，直至待排序集合只剩下一个元素为止，然后不断合并两个排好序的数组段templateclassTypevoidMergeSort(Typea[],intleft,intright){if(leftright)//控制待排序数组中至少有两个元素{inti=(left+right)/2;//取数组中点，将数组尽量均等划分MergeSort(a,left,i);//将左半段进行递归排序MergeSort(a,i+1,right);//将右半段进行递归排序Mer