<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                ??碼云GVP開源項目 12k star Uniapp+ElementUI 功能強大 支持多語言、二開方便! 廣告
                ## 10.3 分治法 分治法(divide-and-conquer)是解決問題的一種常用策略,其思想是將難以處理的較大 問題分解為若干個較小的子問題,然后分別解決這些子問題,并從子問題的解構造出原問題 的解。“分”是指將原問題分解,“治”是指解決問題。 “分治”僅提及了分而治之的過程,而未提及此方法的另一個特點——遞歸。當我們將 大問題分解成子問題后,經常會發現子問題與大問題本質上是相同的問題,因此可以利用遞 歸方法來設計算法。所以,分治法常常與遞歸法結合起來使用。 下面我們通過排序問題來介紹分治法的應用。排序問題是指將一個數據集合中的所有數 據按從小到大的順序(嚴格遞增或非遞減)重新排列①。計算機科學家發明了很多排序算法, 本節主要介紹利用分而治之思想設計的歸并排序算法,但為了進行比較,我們先介紹沒有什 么“技術含量”的選擇排序算法。 選擇排序 選擇排序是一種樸素的排序方法,普通人都很容易想到。其思想是:先從全體 n 個數據 中找出最小值,并將該最小值排在第一個位置;然后從剩下的 n-1 個數據中再次找出最小值,這個最小值實際上是全體數據的次小值,我們將它排在第二個位置;依此類推,直至從剩下 的 2 個數據中找出最小值,排在第 n-1 個位置,而剩下的最后一個數據(全體數據中的最大 值)可以直接排在第 n 個位置。 > ① 當然也可以按從大到小的順序(嚴格遞減或非遞增)排列,這在解決方法上并沒有什么本質差別。 選擇排序方法的關鍵步驟是找出當前剩余數據中的最小值。我們在 3.6 節中討論過這個 問題①,并且設計了一個很好的算法:逐個檢查每一個數據,并記錄當前見到的最小值;當 數據檢查完畢,所記錄的數據就是全體數據中的最小值。下面我們利用這個求最小值的方法 來實現選擇排序算法。 算法的核心部分是一個循環,每一輪循環找出剩余數據中的最小值,并將該值放到合適 位置。假設數據在列表 list 中,則第一次循環找出 list[0:n-1]中的最小值,并將該值存入 list[0] 處(原來的 list[0]數據需要挪地方,見下面介紹的實現技巧)。第二次循環從 list[1:n-1]中找 出最小值,并存入 list[1]處;依此類推,第 n-1 次循環將 list[n-2:n-1]中的最小值存入 list[n-2], 而剩下的最后一個數據自然只能存入 list[n-1]。至此,list 中存儲的數據即為從小到大有序 排列的。 實現此算法時,如果沒有額外的存儲空間,只使用 list 本身的空間來排序,則在第一次 循環中將最小值放入 list[0]時,原先存儲在其中的數據就會被覆蓋。為了保留這個數據,一 個簡單的技巧是將 list[0]與找到的最小值交換。即,假如最小值是 list[k],則執行 ``` list[0],list[k] = list[k],list[0] ``` 其他輪次的處理也是一樣。為此,在循環中需要用一個變量記錄最小值的位置索引。 下面的 Python 代碼實現了以上設計思想,其中每輪循環找出 list[i:n-1]中的最小值(用變量 min 記錄其索引位置),并放入 list[i]中。 ``` >>> def selSort(list): n = len(list) for i in range(n-1): min = i for j in range(i+1,n): if list[j] < list[min]: min = j list[i],list[min] = list[min],list[i] >>> datalist = [5,2,8,3,4] >>> selSort(datalist) >>> print datalist [2, 3, 4, 5, 8] ``` 注意,與 3.6 中最小值算法不同的是,這里找最小值時并非記錄最小值本身,而是記錄最小 值的索引位置 min,即 list[min]才是當前最小值,這是為了使列表數據交換位置更方便。另 外,循環變量 i 只需從 0 取到 n-2,因為當前 n-1 個數據就位后,最后一個位置自然就是最 大值。 選擇排序算法很容易設計實現,并且當數據量不大時效率也還可以,但當數據量很大時 性能很差。采用分治法可以設計一種更好的排序算法,即歸并排序。 > ① 3.6 中討論的是求最大值,但算法稍加改變即可用于求最小值。 歸并排序 人們在玩撲克牌的時候,經常將手上的牌排成特定的順序,比如按花色或按大小排序。 如果分到的牌不多,玩家一般用一只手將牌呈扇形握持,另一只手去整理排序。然而,如果 玩的是用到兩三副牌的游戲,每個玩家分到的牌很多,那么玩家就會有手太小難以排序的煩 惱。這時,如果旁邊坐著個觀戰者,玩家可以請這個觀戰者幫著拿一些牌,兩人分別將手中 不多的牌進行排序,然后再合并兩手牌以完成全部牌的排序。這就是歸并排序的基本思想, 它將大任務分解成較小任務,解決了較小任務后再合并結果。下面我們詳細介紹這種利用分 治法進行排序的方法。 給定一個較大的數據集合 S,先將數據平分為兩部分 S1 和 S2,然后分別對 S1 和 S2 進行 排序,從而得到兩個“局部有序”的序列。接下去將這兩個局部有序序列合并成為“全局有 序”序列,這個過程稱為歸并(merge)。假設用序列 S3 存儲歸并結果,則具體歸并方法是: 第一輪,兩個局部有序的序列 S1 和 S2 分別拿出自己的局部最小值進行比較,其中更小者顯 然是全局最小值,因此應放入 S3 的第一個位置。如果全局最小值來自 S1,則 S1 中原來排在 該最小值后面的數據成為新的局部最小值。第二輪,再次比較 S1 和 S2 的局部最小值,其中 更小者實際上是全局第二小的數據,因此應放入 S3 的第二個位置。第三輪以下依此類推, 不斷比較 S1 和 S2 的局部最小值,并將更小者放入 S3,直至 S1(或 S2)的所有數據都已放入 S3。最后,只需將 S2(或 S1)的剩余數據按序放入 S3 的尾部,即可得到全局有序序列。圖 10.5 用整理撲克牌的例子展示了這個歸并排序過程。 ![](https://box.kancloud.cn/2016-02-22_56cafce759b20.png) ![](https://box.kancloud.cn/2016-02-22_56cafce77abe3.png) 圖 10.5 歸并排序 下面是對圖 10.5 所示過程的簡要解釋: (a) 無序的初始撲克牌集合,牌太多導致難以一手進行排序; (b) 一分為二,玩家和幫忙者兩人各持一半牌; (c) 兩人分別對手中牌進行排序,從而得到兩手局部有序的撲克牌序列; (d) 兩人比較各自手中的局部最小牌(黑桃 2 和方塊 3),其中更小的黑桃 2 是全局最小 牌,將它放到存放歸并結果的某個地方(比如桌子上); (e)(f)(g) 重復(d)的做法,相繼將方塊 3、梅花 5 和梅花 6 放到歸并結果序列中; (h) 由于第二個序列已經沒有牌了,故將第一個序列剩余的牌接在歸并結果序列之后。 至此形成了全局有序序列。 通過圖 10.5 的形象化演示,相信讀者已經理解歸并過程。現在還有一個問題:圖 10.5(c) 是對圖 10.5(b)的兩手牌分別進行“排序”后得到的,問題是怎么排序?顯然,我們又回到 了初始的“排序”問題,只不過這次的排序問題具有較小的規模:初始問題是對 6 張牌排序, 現在只需兩人分別對自己的 3 張牌排序。這讓我們想起了“遞歸”這個設計利器。是的,如果覺得 3 張牌還是太多,那么可以重復上述一分為二、局部排序、全局歸并的過程。這個過程可以一直進行到只有 1 張牌的情形,這時根本無需排序,因為 1 張牌自然是局部有序的。 這樣就得到了遞歸的奠基情形,此時無需遞歸,只需歸并。由于滿足了每次遞歸數據規模減 小和有奠基情形這兩個條件,上述遞歸過程是正確的。歸并排序算法的偽代碼如下,其中劃 線部分表現了該算法的遞歸結構。 算法:對 datalist 執行歸并排序 輸入:無序的列表 datalist 輸出:有序的列表 datalist 將 datalist 一分為二:list1 和 list2 對 list1 執行歸并排序 對 list2 執行歸并排序 歸并 list1 和 list2,結果放入 datalist 下面我們用 Python 編制一個完整的程序來實現并排序算法。程序 10.1 主要由兩個函數 構成:函數 merge 用于歸并兩個局部有序的列表 list1 和 list2,結果放在 mergelist 中;函數 mergeSort 則利用分治法和遞歸實現對列表 datalist 的排序。 【程序 10.1】mergesort.py ``` def merge(list1,list2,mergelist): i,j,k = 0,0,0 n1,n2 = len(list1),len(list2) while i < n1 and j < n2: if list1[i]&lt;list2[j]: mergelist[k] = list1[i] i = i + 1 else: mergelist[k] = list2[j] j = j + 1 k = k + 1 while i < n1: mergelist[k] = list1[i] i = i + 1 k = k + 1 while j < n2: mergelist[k] = list2[j] j = j + 1 k = k + 1 def mergeSort(datalist): n = len(datalist) if n > 1: m = n / 2 list1,list2 = datalist[:m],datalist[m:] mergeSort(list1) mergeSort(list2) merge(list1,list2,datalist) data = [9,2,7,6,5,3] mergeSort(data) print data ``` 執行程序 10.1,將在屏幕上看到輸出: ``` [2, 3, 5, 6, 7, 9] ``` 順便提醒讀者注意:程序 10.1 中,函數 mergeSort 的形參 datalist 是列表類型,調用時 我們傳遞列表 data 作為實參。由于函數對列表類型的實參的修改后果是可以帶出函數的①, 所以當我們將無序的 data 傳給 mergeSort,等 mergeSort 執行完畢,data 就變成有序的了。 前面介紹的二分搜索算法其實也是分治法的應用,只不過將數據平分為兩部分之后,只 需“治”其中一部分,另一部分可以忽略。后面的 Hanoi 塔問題也是分治法的應用。 最后小結一下分治法。解決一個問題時,經常將問題分解為較小的問題,小問題和大問 題是同類問題。解決了小問題之后,將部分解合并,形成初始問題的最終解。如果小問題完 全類似于初始問題,只是規模較小,顯然可以用遞歸法設計算法。
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看