资源描述：
《分治策略在归并排序中的算法设计》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、分治策略在归并排序中的算法设计■设计论文分治策略在归并排序中的算法设计李六杏(安徽经济管理学院,安徽合月巴230031)摘要：分治是一种解题的策略，它的基本思想是分而治之•归并排序法是将已有序的子序列合并，得到完全有序的序列•在各种排序方法中,如归并排序、堆排序、快速排序等，都存在有分治的思想•归并排序法是采用分治法的一个非常典型的应用.本文利用分治策略对归并排序进行算法设计，并与其它算法分析比较.关键词:分治策略；归并排序；算法设计；比较优势中图分类号：TP311.1文献标识码：A文章编号：1673-260X(2015)
2、08-0021-03分治策略即算法设计中的分治法.它的基本思想：对于那些规模较大的问题,我们难以直接解决，通常将其分解成若干个相互独立、易于解决的小问题，然后再通过递归算法，求出这些子问题，将这些子问题进行合并后的解，即可得到较大的原问题的答案.分治策略就是通过减小问题的规模，将大的问题化解成若干个小问题后逐步求解，这样能够大大降低了问题的复杂程度，提高了解决问题的效率.本文利用分治策略对归并排序进行改进算法设计，并与其它算法进行分析比较.1分治策略的适用条件分而治之是一种解题的方法，其基本思路是：〃如果一个大问题比较复杂
3、,就可以将这个问题分解，然后各个击破•〃分治从字面上包含了〃分〃和〃治〃两层含义,那么如何分，分后又如何〃治〃就成为我们解决问题的关键之处.通常并不是所有的问题都可以采用分治策略，只有那些能将问题分解成与原问题相似的、意思接近的子问题,并且再合并以后依然符合原问题的意思的这些问题,才能适用分治策略⑴•一般的,能够使用分治算法解决的问题有以下几点特征:(1)此问题在规模上可以缩小到一走的程度就能很容易地解决.一般的问题都能满足这个条件，这是因为一般问题的计算复杂性都是随着问题规模的增大而增大；(1)此问题能够分解成若干个类似
4、的规模较小的问题，也即该问题能够分解成若干个子问题来解决.这是分治策略应用的前提，一般大多数问题都是可以满足的，这个特征充分反映了分治策略中递归思想的应用；(2)若干个分解出的子问题的解能够合并为原问题的解；这一点是关键,能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑用贪心法或动态规划法;(3)此问题分解得出的若干子问题必须是相互独立，即分解的子问题相互之间不存在公共的子子问题•这就涉及到分治策略的使用效率，如果各个子问题相互之间是不独立的，有共性部分，则分治法
5、就要做许多重复的工作，公共的子问题被重复地解决，此时虽然可以使用分治算法，但其效率较低，这时反而使用动态规划算法较好.2分治算法解析在使用分治策略算法解决问题时，一般分为三个步骤操作•第一步，划分问题:首先将要解决的复杂问题分解成若干个较简单的同类型的小问题.在问题划分时，可以采取递归策略，即扌巴一个规模大的问题逐步分解到若干个规模较小的子问题，直至分解成可以很轻松的直接求出这些子问题的解；然后将这些子问题逐层一级一级的合并，直至返回到最上层，即可得出原问题的解.根据分治策略划分问题的原则,一般的，每层可划分成两个子问题，
6、并且这两个子问题在规模差不多最好•在逆向合并求解时要根据问题而异，有些问题逐层递归分解完后就能得到原问题的解，而有些问题可能需要先逐层的进行合并,原问题的解才可能得到•第二步,递归求解：当子问题经过层层划分到足够小时，轻松求解出最小子问题的解•第三步，合并问题：将已解决的下层子问题的解再逐层向上合并，最终得到原问题的解答.由上所述，分治算法的设计过程如下图1所示.图1分治算法设计过程分治的框架结构如下：procedureDivideQif问题不可分then//直接解决直接求解；返回问题的解;endelse对原问题进行分治；
7、〃划分问题通过递归对每一个分治的小部分进行求解;〃递归求解逐层合并到解决整个问题•最后得出问题的求解;〃合并问题end;end;在数据结构的排序算法中”归并排序效率较高.归并排序算法描述:通过将已经有序的若干个子序列合并，最后得出完全有序的序列•对一个没有排好序的序列进行排序,首先使用分割的方法先将大序列分割成一个个已排好序的小序列,利用归并的方法，再将排好序的子序列合并成一个完整的排好序的序列[2]以上正好符合分治策略的思想，在诸多的排序算法中，例如堆排序、归并排序、快速排序等等，都存在有分而治之的思想•而归并（Merg
8、e）排序算法是采用分治策略（DivideandConquer）的典型的应用.下面以实例加以分析比较，问题描述如下:3.1已知某数列存储在序列A⑴,A[2]A[n],拟采用分治策略对它们进行排序（从小到大或从大到小）.例如:104638257排序后为:234567810按照分治策略的三步法，对归并排序问题
