分治策略在归并排序中算法设计方案

1、分治策略在归并排序中的算法设计- 设计论文分治策略在归并排序中的算法设计李六杏（安徽经济管理学院，安徽合肥 230031 ）摘 要：分治是一种解题的策略，它的基本思想是分而治之.归并排序法是将已有序的子序列合并，得到完全有序的序列.在各种排序方法中，如归并排序、堆排序、快速排序等，都存在有分治的思想.归并排序法是采用分治法的一个非常典型的应用 .本文利用分治策略对归并排序进行算法设计，并与其它算法分析比较 .关键词：分治策略；归并排序；算法设计；比较优势中图分类号： TP311.1 文献标识码： A 文章编号： 1673-260X （2015 ） 08-0021-03分治策略即算法设计中的分治

2、法.它的基本思想：对于那些规模较大的问题，我们难以直接解决，通常将其分解成若干个相互独立、易于解决的小问题，然后再通过递归算法，求出这些子问题，将这些子问题进行合并后的解，即可得到较大的原问题的答案.分治策略就是通过减小问题的规模，将大的问题化解成若干个小问题后逐步求解，这样能够大大降低了问题的复杂程度，提高了解决问题的效率 .本文利用分治策略对归并排序进行改进算法设计，并与其它算法进行分析比较 .1 分治策略的适用条件分而治之是一种解题的方法，其基本思路是：“如果一个大问题比较复杂，就可以将这个问题分解，然后各个击破. ”分治从字面上包含了“分”和“治”两层含义，那么如何分，分后又如何“治”

3、就成为我们解决问题的关键之处.通常并不是所有的问题都可以采用分治策略，只有那些能将问题分解成与原问题相似的、意思接近的子问题，并且再合并以后依然符合原问题的意思的这些问题，才能适用分治策略 1. 一般的，能够使用分治算法解决的问题有以下几点特征：（1）此问题在规模上可以缩小到一定的程度就能很容易地解决.一般的问题都能满足这个条件，这是因为一般问题的计算复杂性都是随着问题规模的增大而增大；（2 ）此问题能够分解成若干个类似的规模较小的问题，也即该问题能够分解成若干个子问题来解决.这是分治策略应用的前提，一般大多数问题都是可以满足的，这个特征充分反映了分治策略中递归思想的应用；（3 ）若干个分解出

4、的子问题的解能够合并为原问题的解；这一点是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑用贪心法或动态规划法；（4 ）此问题分解得出的若干子问题必须是相互独立，即分解的子问题相互之间不存在公共的子子问题.这就涉及到分治策略的使用效率，如果各个子问题相互之间是不独立的，有共性部分，则分治法就要做许多重复的工作，公共的子问题被重复地解决，此时虽然可以使用分治算法，但其效率较低，这时反而使用动态规划算法较好 .2 分治算法解读在使用分治策略算法解决问题时，一般分为三个步骤操作.第一步，划分问题：首先将要解决的复杂问题分解成若干个较简

5、单的同类型的小问题.在问题划分时，可以采取递归策略，即把一个规模大的问题逐步分解到若干个规模较小的子问题，直至分解成可以很轻松的直接求出这些子问题的解；然后将这些子问题逐层一级一级的合并，直至返回到最上层，即可得出原问题的解.根据分治策略划分问题的原则，一般的，每层可划分成两个子问题，并且这两个子问题在规模差不多最好 .在逆向合并求解时要根据问题而异，有些问题逐层递归分解完后就能得到原问题的解，而有些问题可能需要先逐层的进行合并，原问题的解才可能得到 .第二步，递归求解：当子问题经过层层划分到足够小时，轻松求解出最小子问题的解 .第三步，合并问题：将已解决的下层子问题的解再逐层向上合并，最终得

6、到原问题的解答.由上所述，分治算法的设计过程如下图1 所示 .3 分治策略在归并排序中的算法设计在数据结构的排序算法中，归并排序效率较高 .归并排序算法描述：通过将已经有序的若干个子序列合并，最后得出完全有序的序列.对一个没有排好序的序列进行排序，首先使用分割的方法先将大序列分割成一个个已排好序的小序列，利用归并的方法，再将排好序的子序列合并成一个完整的排好序的序列2.以上正好符合分治策略的思想，在诸多的排序算法中，例如堆排序、归并排序、快速排序等等，都存在有分而治之的思想.而归并（ Merge ）排序算法是采用分治策略（DivideandConquer ）的典型的应用.下面以实例加以分析比较

7、，问题描述如下：3.1 已知某数列存储在序列A1 ， A2 ， ，An ，拟采用分治策略对它们进行排序（从小到大或从大到小）.例如：104638257排序后为：234567810按照分治策略的三步法，对归并排序问题解决如下：划分问题：把这组序列分成元素个数尽可能相等的两部分；递归问题：把两半元素分别排序；合并问题：把两个已有序的序列合并成一个序列.如图 2 所示.划分问题与递归问题这两部分较易完成，关键在于第三步，如何把两个有序序列合并成一个有序序列.图 3 给出了一个合并的过程：把两个有序表中的最小元素加以比较后，选取其中的较小元素删除，并加入合并后的新表中，重复多次即可 .3.2 归并排序

8、的变形求逆序对数目给定一整数数组A= （A1 ，A2 ， An ），若 ij 且 AiAj ，则 i，j 就为一个逆序对 .例如数组（ 3，1，4， 5，2）的逆序对有3，1，3，2，4，2，5，2.问题 求解 ：输 入n和A数 组， 要求 统计 出逆 序对 的数 目 . 数 据范 围 ：1=n=1000000.分析本题，很容易想到一个非常简单的算法穷举算法，即对数组中任意的两个数组元素进行分析判断，看它们能否构成“逆序对”. 这种算法完全可行，但它的时间复杂度为O （ N2 ） .时间效率不尽如人意 .考虑采用分治求解：·划分问题：把数组分成元素个数尽可能相等的两部分；·

9、递归求解：求解划分后的逆序对数目（ i 和 j 都在左边或者都在右边）；·合并问题：合并求解逆序对数目（ i 在左边但 j 在右边） .记数列 aLaR 的逆序对数目为d （L，R）； mid= （L+R ）/2 ，则有： d（ L， R）=d （ L，mid ）+d （mid+1 ， Rd） +F （ L， mid ， R） .其中 F（ L，mid ， R）表示一个数取自aL ，mid ，另一个数取自amid+1， R时所构成的逆序对数目 .和上面介绍的归并排序一样，划分部分和递归求解部分都较简单，关键在于如何合并怎样求出i 在左边而 j 在右边的逆序对数目？统计的常见技巧是“分

10、类”. 首先按j照的不同对这些分布两边的逆序对进行分类：即对于右边的每个 j ，我们统计左边比它大的元素的个数f （j），然后将所有f（ j）相加，其和即是答案 .以上的归并排序同时完成了f （j ）的计算：因为最后的合并操作是从小到大进行排序的，也即当右边的aj 复制到临时变量temp中时，左边还未复制到temp的那些数就是左边所有比aj 大的数 .此时的累加和中再加上左边元素个数 mid-i+1 即为答案 .即把 if （aiaj ） thenbegintempp ：=aj ； inc （p ）； inc （ j）；end改为“if aiaj（ ） thenbegintot ：=tot+mid-i+1； tempp：=aj ； inc （p ）； inc （ j）；end在上例中，通过分析利用穷举算法和分治算法比较之，分治算法的优势显而易见 .4 小结在各种排序算法中，如堆排序、归并排序、快速排序等，利用分治策略的归并排序效率较高 .若数列长设为N ，将大数列分解成若干小数列共需logN步，其中每步都是合并有序数列的过程，其时间复杂度为O （ N ），故一共为O（ N*logN ） .由于归并排序每次操作均在相邻的数据中进行，所以归并排序在时间复杂度为 O （N*logN ）的几种排序算法中效率较高 3.参考文献