1、 分治策略在歸并排序中的算法設(shè)計(jì)-設(shè)計(jì)論文 分治策略在歸并排序中的算法設(shè)計(jì) 李六杏 ） （安徽經(jīng)濟(jì)管理學(xué)院，安徽合肥 230031歸并排序法是將摘 要：分治是一種解題的策略，它的基本思想是分而治之.在各種排序方法中，如歸并排序、已有序的子序列合并，得到完全有序的序列.歸并排序法是采用分治法的一個(gè)非堆排序、快速排序等，都存在有分治的思想.本文利用分治策略對(duì)歸并排序進(jìn)行算法設(shè)計(jì)，并與其它算法分析常典型的應(yīng)用. 比較 關(guān)鍵詞 ：分治策略；歸并排序；算法設(shè)計(jì)；比較優(yōu)勢(shì)08- ）20151673-260XA 中圖分類號(hào)：TP311.1文獻(xiàn)標(biāo)識(shí)碼：文章編號(hào)：（0021-03 它的基本思想：對(duì)于那些規(guī)模較大

2、的問(wèn)題，. 分治策略即算法設(shè)計(jì)中的分治法我們難以直接解決，通常將其分解成若干個(gè)相互獨(dú)立、易于解決的小問(wèn)題，然后再通過(guò)遞歸算法，求出這些子問(wèn)題，將這些子問(wèn)題進(jìn)行合并后的解，即可得分治策略就是通過(guò)減小問(wèn)題的規(guī)模，將大的問(wèn)題化解成.到較大的原問(wèn)題的答案若干個(gè)小問(wèn)題后逐步求解，這樣能夠大大降低了問(wèn)題的復(fù)雜程度，提高了解決本文利用分治策略對(duì)歸并排序進(jìn)行改進(jìn)算法設(shè)計(jì)，并與其它算法進(jìn).問(wèn)題的效率. 行分析比較 分治策略的適用條件 1 分而治之是一種解題的方法，其基本思路是：“如果一個(gè)大問(wèn)題比較復(fù)雜， 就可以將這個(gè)問(wèn)題分解，然后各個(gè)擊破.”分治從字面上包含了“分”和“治”通.兩層含義，那么如何分，分后又如何“

3、治”就成為我們解決問(wèn)題的關(guān)鍵之處常并不是所有的問(wèn)題都可以采用分治策略，只有那些能將問(wèn)題分解成與原問(wèn)題相似的、意思接近的子問(wèn)題，并且再合并以后依然符合原問(wèn)題的意思的這些問(wèn)一般的，能夠使用分治算法解決的問(wèn)題有以下幾點(diǎn)特題，才能適用分治策略1. 征：一般的問(wèn)題 ）此問(wèn)題在規(guī)模上可以縮小到一定的程度就能很容易地解決1.（都能滿足這個(gè)條件，這是因?yàn)橐话銌?wèn)題的計(jì)算復(fù)雜性都是隨著問(wèn)題規(guī)模的增大 而增大；）此問(wèn)題能夠分解成若干個(gè)類似的規(guī)模較小的問(wèn)題，也即該問(wèn)題能夠分 （2 這是分治策略應(yīng)用的前提，一般大多數(shù)問(wèn)題都是可以解成若干個(gè)子問(wèn)題來(lái)解決. 滿足的，這個(gè)特征充分反映了分治策略中遞歸思想的應(yīng)用；）若干個(gè)分解出

4、的子問(wèn)題的解能夠合并為原問(wèn)題的解；這一點(diǎn)是關(guān)鍵，3 （能否利用分治法完全取決于問(wèn)題是否具有第三條特征，如果具備了第一條和第 二條特征，而不具備第三條特征，則可以考慮用貪心法或動(dòng)態(tài)規(guī)劃法；）此問(wèn)題分解得出的若干子問(wèn)題必須是相互獨(dú)立，即分解的子問(wèn)題相互 （4 這就涉及到分治策略的使用效率，如果各個(gè)子問(wèn)題之間不存在公共的子子問(wèn)題.相互之間是不獨(dú)立的，有共性部分，則分治法就要做許多重復(fù)的工作，公共的子問(wèn)題被重復(fù)地解決，此時(shí)雖然可以使用分治算法，但其效率較低，這時(shí)反而. 使用動(dòng)態(tài)規(guī)劃算法較好 2 分治算法解讀第一步，劃分問(wèn).在使用分治策略算法解決問(wèn)題時(shí)，一般分為三個(gè)步驟操作 在問(wèn)題劃.題：首先將要解決的

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

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

7、er 較，問(wèn)題描述如下：，擬采用分治策略對(duì)它，已知某數(shù)列存儲(chǔ)在序列 3.1 A1，A2An. 們進(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所示 劃分問(wèn)題與遞歸問(wèn)題這兩部分較易完成，關(guān)鍵在于第三步，如何把兩個(gè)有序 給出了一個(gè)合并的過(guò)程：把兩個(gè)有序表中的最小3圖.序列合并成一個(gè)有序序列元素加以比較后，選取其中的較小元素刪除，并加入合并后

8、的新表中，重復(fù)多. 次即可 歸并排序的變形求逆序?qū)?shù)目 3.2 就為一個(gè)逆，j 給定一整數(shù)數(shù)組A=（A1，A2，An），若ij且AiAj，則i 問(wèn)，2.，4，25，）的逆序?qū)τ?1.序?qū)鐢?shù)組（3，4，5，23，13，2：目序逆對(duì)的數(shù).數(shù)據(jù)范圍出統(tǒng)要組An輸解題求：入和數(shù)，求計(jì)1=n=1000000. 分析本題，很容易想到一個(gè)非常簡(jiǎn)單的算法窮舉算法，即對(duì)數(shù)組中任意的兩 個(gè)數(shù)組元素進(jìn)行分析判斷，看它們能否構(gòu)成“逆序?qū)Α?這種算法完全可行，但. .時(shí)間效率不盡如人意）（它的時(shí)間復(fù)雜度為ON2 考慮采用分治求解： ·劃分問(wèn)題：把數(shù)組分成元素個(gè)數(shù)盡可能相等的兩部分； 都在左邊或者都在右邊）

9、；i和j ·遞歸求解：求解劃分后的逆序?qū)?shù)目（. 在右邊）i在左邊但j ·合并問(wèn)題：合并求解逆序?qū)?shù)目（d）/2，則有：， 記數(shù)列aLaR的逆序?qū)?shù)目為d（LR）；mid=（L+R，midmid+1，mid）+d（，Rd）+F（L，R）.其中F（L=dL（，R）（L時(shí)所構(gòu)成mid，R）表示一個(gè)數(shù)取自aL，amid+1R，mid，另一個(gè)數(shù)取自和上面介紹的歸并排序一樣，劃分部分和遞歸求解部分都較簡(jiǎn)的逆序?qū)?shù)目.在右邊的逆序?qū)?shù)目？統(tǒng)計(jì)的常見(jiàn)單，關(guān)鍵在于如何合并怎樣求出i在左邊而j的不同對(duì)這些分布兩邊的逆序?qū)M(jìn)行分類：即對(duì)于技巧是“分類”.首先按照j）相，我們統(tǒng)計(jì)左邊比它大的元素

10、的個(gè)數(shù)右邊的每個(gè)jf（j），然后將所有f（j. 加，其和即是答案）的計(jì)算：因?yàn)樽詈蟮暮喜⒉僮魇菑男〉酱骹 以上的歸并排序同時(shí)完成了（j中時(shí)，左邊還未復(fù)制到temp進(jìn)行排序的，也即當(dāng)右邊的aj復(fù)制到臨時(shí)變量此時(shí)的累加和中再加上左邊元素個(gè).temp的那些數(shù)就是左邊所有比aj大的數(shù). 即為答案數(shù)mid-i+1 ）；（ incjp；begin aiaj 即把if（） then tempp：=aj inc（）；end then 改為“if （aiaj） j）；（ pinc；： =tot+mid-i+1tot begin ：；tempp=aj （）；incend 在上例中，通過(guò)分析利用窮舉算法和分治算法比較之，分治算法的優(yōu)勢(shì)顯而 . 易見(jiàn) 4 小結(jié)在各種排序算法中，如堆排序、歸并排序、快速排序等，利用分治策略的歸 步，N，將大數(shù)列分解成若干小數(shù)列共需logN并排序效率較高.若數(shù)列長(zhǎng)設(shè)為ON），故一共為其中每步都是合并有序數(shù)列的過(guò)程，其時(shí)間復(fù)雜度為O（由于歸并排序每次操作均在相鄰的數(shù)據(jù)中進(jìn)行，所以歸并排序在）.（N*logN3. ）的幾種排序算法中效率較高N*logN時(shí)間復(fù)雜