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

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

《分治策略在归并排序中算法设计方案.docx》由会员分享，可在线阅读，更多相关《分治策略在归并排序中算法设计方案.docx（6页珍藏版）》请在冰点文库上搜索。

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

分治策略在归并排序中的算法设计-设计论文

分治策略在归并排序中的算法设计李六杏（安徽经济管理学院，安徽合肥230031）摘要：

分治是一种解题的策略，它的基本思想是分而治之.归并排序法是将已有序的子序列合并，得到完全有序的序列.在各种排序方法中，如归并排序、堆排序、快速排序等，都存在有分治的思想.归并排序法是采用分治法的一个非常典型的应用.本文利用分治策略对归并排序进行算法设计，并与其它算法分析比较.关键词：

分治策略；归并排序；算法设计；比较优势中图分类号：

TP311.1文献标识码：

A文章编号：

1673-260X（2015）08-0021-03分治策略即算法设计中的分治法.它的基本思想：

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

“如果一个大问题比较复杂，就可以将这个问题分解，然后各个击破.”分治从字面上包含了“分”和“治”两层含义，那么如何分，分后又如何“治”就成为我们解决问题的关键之处.通常并不是所有的问题都可以采用分治策略，只有那些能将问题分解成与原问题相似的、意思接近的子问题，并且再合并以后依然符合原问题的意思的这些问题，才能适用分治策略[1].一般的，能够使用分治算法解决的问题有以下几点特征：

（1）此问题在规模上可以缩小到一定的程度就能很容易地解决.一般的问题都能满足这个条件，这是因为一般问题的计算复杂性都是随着问题规模的增大而增大；

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

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

当子问题经过层层划分到足够小时，轻松求解出最小子问题的解.第三步，合并问题：

将已解决的下层子问题的解再逐层向上合并，最终得到原问题的解答.由上所述，分治算法的设计过程如下图1所示.

3分治策略在归并排序中的算法设计在数据结构的排序算法中，归并排序效率较高.归并排序算法描述：

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

3.1已知某数列存储在序列A[1]，A[2]，……，A[n]，拟采用分治策略对它们进行排序（从小到大或从大到小）.例如：

104638257排序后为：

234567810按照分治策略的三步法，对归并排序问题解决如下：

划分问题：

把这组序列分成元素个数尽可能相等的两部分；递归问题：

把两半元素分别排序；合并问题：

把两个已有序的序列合并成一个序列.如图2所示.

划分问题与递归问题这两部分较易完成，关键在于第三步，如何把两个有序序列合并成一个有序序列.图3给出了一个合并的过程：

把两个有序表中的最小元素加以比较后，选取其中的较小元素删除，并加入合并后的新表中，重复多次即可.

3.2归并排序的变形求逆序对数目给定一整数数组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）.时间效率不尽如人意.

考虑采用分治求解：

·划分问题：

把数组分成元素个数尽可能相等的两部分；·递归求解：

求解划分后的逆序对数目（i和j都在左边或者都在右边）；·合并问题：

合并求解逆序对数目（i在左边但j在右边）.记数列a[L]~a[R]的逆序对数目为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）表示一个数取自a[L，mid]，另一个数取自a[mid+1，R]时所构成的逆序对数目.和上面介绍的归并排序一样，划分部分和递归求解部分都较简单，关键在于如何合并怎样求出i在左边而j在右边的逆序对数目？

统计的常见技巧是“分类”.首先按照j的不同对这些分布两边的逆序对进行分类：

即对于右边的每个j，我们统计左边比它大的元素的个数f（j），然后将所有f（j）相加，其和即是答案.以上的归并排序同时完成了f（j）的计算：

因为最后的合并操作是从小到大进行排序的，也即当右边的a[j]复制到临时变量temp中时，左边还未复制到temp的那些数就是左边所有比a[j]大的数.此时的累加和中再加上左边元素个数mid-i+1即为答案.即把if（a[i]a[j]）thenbegintemp[p]：

=a[j]；inc（p）；inc（j）；end改为“if（a[i]a[j]）thenbegintot：

=tot+mid-i+1；temp[p]：

=a[j]；inc（p）；inc（j）；end在上例中，通过分析利用穷举算法和分治算法比较之，分治算法的优势显而易见.4小结在各种排序算法中，如堆排序、归并排序、快速排序等，利用分治策略的归并排序效率较高.若数列长设为N，将大数列分解成若干小数列共需logN步，其中每步都是合并有序数列的过程，其时间复杂度为O（N），故一共为O（N*logN）.由于归并排序每次操作均在相邻的数据中进行，所以归并排序在时间复杂度为O（N*logN）的几种排序算法中效率较高[3].参考文献：

（1）吴文虎.程序设计基础[M].北京：

清华大学出版社，2010.181-194.

（2）吴耀斌，曹利国，等.高级教程系列-信息学奥林匹克教程提高篇[M].湖南：

湖南师范大学出版社，2013.213-229.（3）李六杏.基于隐含条件挖掘的枚举算法优化[J].安徽科技学院学报，2013，27（6）：

66-69.