分治策略在歸并排序中的算法設(shè)計(jì)

李六杏

（安徽經(jīng)濟(jì)管理學(xué)院，安徽 合肥 230031）

分治策略即算法設(shè)計(jì)中的分治法.它的基本思想：對(duì)于那些規(guī)模較大的問(wèn)題，我們難以直接解決，通常將其分解成若干個(gè)相互獨(dú)立、易于解決的小問(wèn)題，然后再通過(guò)遞歸算法，求出這些子問(wèn)題，將這些子問(wèn)題進(jìn)行合并后的解，即可得到較大的原問(wèn)題的答案.分治策略就是通過(guò)減小問(wèn)題的規(guī)模，將大的問(wèn)題化解成若干個(gè)小問(wèn)題后逐步求解，這樣能夠大大降低了問(wèn)題的復(fù)雜程度，提高了解決問(wèn)題的效率.本文利用分治策略對(duì)歸并排序進(jìn)行改進(jìn)算法設(shè)計(jì)，并與其它算法進(jìn)行分析比較.

1 分治策略的適用條件

分而治之是一種解題的方法，其基本思路是：“如果一個(gè)大問(wèn)題比較復(fù)雜，就可以將這個(gè)問(wèn)題分解，然后各個(gè)擊破.”分治從字面上包含了“分”和“治”兩層含義，那么如何分，分后又如何“治”就成為我們解決問(wèn)題的關(guān)鍵之處.通常并不是所有的問(wèn)題都可以采用分治策略，只有那些能將問(wèn)題分解成與原問(wèn)題相似的、意思接近的子問(wèn)題，并且再合并以后依然符合原問(wèn)題的意思的這些問(wèn)題，才能適用分治策略[1].一般的，能夠使用分治算法解決的問(wèn)題有以下幾點(diǎn)特征：

（1）此問(wèn)題在規(guī)模上可以縮小到一定的程度就能很容易地解決.一般的問(wèn)題都能滿足這個(gè)條件，這是因?yàn)橐话銌?wèn)題的計(jì)算復(fù)雜性都是隨著問(wèn)題規(guī)模的增大而增大；

（2）此問(wèn)題能夠分解成若干個(gè)類似的規(guī)模較小的問(wèn)題，也即該問(wèn)題能夠分解成若干個(gè)子問(wèn)題來(lái)解決.這是分治策略應(yīng)用的前提，一般大多數(shù)問(wèn)題都是可以滿足的，這個(gè)特征充分反映了分治策略中遞歸思想的應(yīng)用；

（3）若干個(gè)分解出的子問(wèn)題的解能夠合并為原問(wèn)題的解；這一點(diǎn)是關(guān)鍵，能否利用分治法完全取決于問(wèn)題是否具有第三條特征，如果具備了第一條和第二條特征，而不具備第三條特征，則可以考慮用貪心法或動(dòng)態(tài)規(guī)劃法；

（4）此問(wèn)題分解得出的若干子問(wèn)題必須是相互獨(dú)立，即分解的子問(wèn)題相互之間不存在公共的子子問(wèn)題.這就涉及到分治策略的使用效率，如果各個(gè)子問(wèn)題相互之間是不獨(dú)立的，有共性部分，則分治法就要做許多重復(fù)的工作，公共的子問(wèn)題被重復(fù)地解決，此時(shí)雖然可以使用分治算法，但其效率較低，這時(shí)反而使用動(dòng)態(tài)規(guī)劃算法較好.

2 分治算法解析

在使用分治策略算法解決問(wèn)題時(shí)，一般分為三個(gè)步驟操作.第一步，劃分問(wèn)題：首先將要解決的復(fù)雜問(wèn)題分解成若干個(gè)較簡(jiǎn)單的同類型的小問(wèn)題.在問(wèn)題劃分時(shí)，可以采取遞歸策略，即把一個(gè)規(guī)模大的問(wèn)題逐步分解到若干個(gè)規(guī)模較小的子問(wèn)題，直至分解成可以很輕松的直接求出這些子問(wèn)題的解；然后將這些子問(wèn)題逐層一級(jí)一級(jí)的合并，直至返回到最上層，即可得出原問(wèn)題的解.根據(jù)分治策略劃分問(wèn)題的原則，一般的，每層可劃分成兩個(gè)子問(wèn)題，并且這兩個(gè)子問(wèn)題在規(guī)模差不多最好.在逆向合并求解時(shí)要根據(jù)問(wèn)題而異，有些問(wèn)題逐層遞歸分解完后就能得到原問(wèn)題的解，而有些問(wèn)題可能需要先逐層的進(jìn)行合并，原問(wèn)題的解才可能得到.第二步，遞歸求解：當(dāng)子問(wèn)題經(jīng)過(guò)層層劃分到足夠小時(shí)，輕松求解出最小子問(wèn)題的解.第三步，合并問(wèn)題：將已解決的下層子問(wèn)題的解再逐層向上合并，最終得到原問(wèn)題的解答.由上所述，分治算法的設(shè)計(jì)過(guò)程如下圖1所示.

圖1 分治算法設(shè)計(jì)過(guò)程

分治的框架結(jié)構(gòu)如下：

3 分治策略在歸并排序中的算法設(shè)計(jì)

在數(shù)據(jù)結(jié)構(gòu)的排序算法中，歸并排序效率較高.歸并排序算法描述：通過(guò)將已經(jīng)有序的若干個(gè)子序列合并，最后得出完全有序的序列.對(duì)一個(gè)沒(méi)有排好序的序列進(jìn)行排序，首先使用分割的方法先將大序列分割成一個(gè)個(gè)已排好序的小序列，利用歸并的方法，再將排好序的子序列合并成一個(gè)完整的排好序的序列[2].以上正好符合分治策略的思想，在諸多的排序算法中，例如堆排序、歸并排序、快速排序等等，都存在有分而治之的思想.而歸并（Merge）排序算法是采用分治策略（Divide and Conquer）的典型的應(yīng)用.下面以實(shí)例加以分析比較，問(wèn)題描述如下：

3.1 已知某數(shù)列存儲(chǔ)在序列A[1]，A[2]，……，A[n]，擬采用分治策略對(duì)它們進(jìn)行排序（從小到大或從大到小）.

例如：10 4 6 3 8 2 5 7

排序后為：2 3 4 5 6 7 8 10

按照分治策略的三步法，對(duì)歸并排序問(wèn)題解決如下：

劃分問(wèn)題：把這組序列分成元素個(gè)數(shù)盡可能相等的兩部分；

遞歸問(wèn)題：把兩半元素分別排序；

合并問(wèn)題：把兩個(gè)已有序的序列合并成一個(gè)序列.如圖2所示.

圖2 歸并排序的分解與合并

劃分問(wèn)題與遞歸問(wèn)題這兩部分較易完成，關(guān)鍵在于第三步，如何把兩個(gè)有序序列合并成一個(gè)有序序列.圖3給出了一個(gè)合并的過(guò)程：把兩個(gè)有序表中的最小元素加以比較后，選取其中的較小元素刪除，并加入合并后的新表中，重復(fù)多次即可.

圖3 歸并排序合并的過(guò)程

歸并算法如下：

3.2 歸并排序的變形——求逆序?qū)?shù)目

給定一整數(shù)數(shù)組A=(A1,A2,…An),若iAj,則 就為一個(gè)逆序?qū)?例如數(shù)組（3，1，4，5，2）的逆序?qū)τ?<3,1>,<3,2>,<4,2>,<5,2>.問(wèn)題求解：輸入n和A數(shù)組，要求統(tǒng)計(jì)出逆序?qū)Φ臄?shù)目.數(shù)據(jù)范圍：1<=n<=1000000.

分析本題，很容易想到一個(gè)非常簡(jiǎn)單的算法——窮舉算法，即對(duì)數(shù)組中任意的兩個(gè)數(shù)組元素進(jìn)行分析判斷，看它們能否構(gòu)成“逆序?qū)Α?這種算法完全可行，但它的時(shí)間復(fù)雜度為O(N2).時(shí)間效率不盡如人意.

考慮采用分治求解:

·劃分問(wèn)題：把數(shù)組分成元素個(gè)數(shù)盡可能相等的兩部分；

·遞歸求解：求解劃分后的逆序?qū)?shù)目（i和j都在左邊或者都在右邊）；

·合并問(wèn)題：合并求解逆序?qū)?shù)目（i在左邊但j在右邊）.

記數(shù)列a[L]~a[R]的逆序?qū)?shù)目為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)表示一個(gè)數(shù)取自a[L,mid]，另一個(gè)數(shù)取自a[mid+1,R]時(shí)所構(gòu)成的逆序?qū)?shù)目.和上面介紹的歸并排序一樣，劃分部分和遞歸求解部分都較簡(jiǎn)單，關(guān)鍵在于如何合并——怎樣求出i在左邊而j在右邊的逆序?qū)?shù)目？統(tǒng)計(jì)的常見(jiàn)技巧是“分類”.首先按照j的不同對(duì)這些分布兩邊的逆序?qū)M(jìn)行分類：即對(duì)于右邊的每個(gè)j，我們統(tǒng)計(jì)左邊比它大的元素的個(gè)數(shù)f(j)，然后將所有f(j)相加，其和即是答案.

以上的歸并排序同時(shí)完成了f(j)的計(jì)算：因?yàn)樽詈蟮暮喜⒉僮魇菑男〉酱筮M(jìn)行排序的，也即當(dāng)右邊的a[j]復(fù)制到臨時(shí)變量temp中時(shí)，左邊還未復(fù)制到temp的那些數(shù)就是左邊所有比a[j]大的數(shù).此時(shí)的累加和中再加上左邊元素個(gè)數(shù)mid-i+1即為答案.

在上例中，通過(guò)分析利用窮舉算法和分治算法比較之，分治算法的優(yōu)勢(shì)顯而易見(jiàn).

4 小結(jié)

在各種排序算法中，如堆排序、歸并排序、快速排序等，利用分治策略的歸并排序效率較高.若數(shù)列長(zhǎng)設(shè)為N，將大數(shù)列分解成若干小數(shù)列共需logN步，其中每步都是合并有序數(shù)列的過(guò)程，其時(shí)間復(fù)雜度為O(N)，故一共為O(N*logN).由于歸并排序每次操作均在相鄰的數(shù)據(jù)中進(jìn)行，所以歸并排序在時(shí)間復(fù)雜度為O(N*logN)的幾種排序算法中效率較高[3].

〔1〕吳文虎.程序設(shè)計(jì)基礎(chǔ)[M].北京：清華大學(xué)出版社，2010.181-194.

〔2〕吳耀斌，曹利國(guó)，等.高級(jí)教程系列-信息學(xué)奧林匹克教程提高篇[M].湖南：湖南師范大學(xué)出版社,2013.213-229.

〔3〕李六杏.基于隱含條件挖掘的枚舉算法優(yōu)化[J].安徽科技學(xué)院學(xué)報(bào),2013，27(6):66-69.