歸並演算法與分而治之

❶ 數據結構--歸並排序與基數排序

一、歸並排序
歸並排序（MERGE-SORT）是利用歸並的思想實現的排序方法，該演算法採用經典的分治（divide-and-conquer）策略（分治法將問題分(divide)成一些小的問題然後遞歸求解，而治(conquer)的階段則將分的階段得到的各答案"修補"在一起，即分而治之)。將兩個或以上的有序表組合成一個新的有序表。
1、2-路歸並排序
初始序列含有n個記錄，可看成n個有序的子序列，每個子序列的長度為1，然後兩兩歸並，得到[n/2]個長度為2或1的有序子序列，再兩兩歸並，如此重復，直至得到一個長度為n的有序序列為止。
2、舉例

上圖中的最後一次合並，要將[4,5,7,8]和[1,2,3,6]兩個已經有序的子序列，合並為最終序列[1,2,3,4,5,6,7,8]，實現步驟：

Tips：
排序演算法的穩定性：保證排序前2個相等的數，在序列中的前後位置順序和排序後它們兩個的前後位置順序相同。例如，Ai = Aj，Ai排序前位於Aj的前面，排序後Ai還位於Aj的前面。
穩定性的好處：排序演算法如果是穩定的，那麼從一個鍵上排序，然後再從另一個鍵上排序，第一個鍵排序的結果可以為第二個鍵排序所用。基數排序就 是這樣，先按低位排序，逐次按高位排序，低位相同的元素其順序再高位也相同時是不會改變的。
排序演算法是否為穩定的是由具體演算法決定的，不穩定的演算法在某種條件下可以變為穩定的演算法，而穩定的演算法在某種條件下也可以變為不穩定的演算法。
例如，對於如下冒泡排序演算法，原本是穩定的排序演算法，如果將記錄交換的條件改成r[j]>=r[j+1]，則兩個相等的記錄就會交換位置，從而變成不穩定的演算法。

堆排序、快速排序、希爾排序、直接選擇排序不是穩定的排序演算法，而基數排序、冒泡排序、直接插入排序、折半插入排序、歸並排序是穩定的排序演算法。

一、基數排序
基數排序是一種藉助多關鍵字排序的思想對單邏輯關鍵字進行排序的方法。
1、什麼是多關鍵字
已知撲克牌中52張牌面的次序關系為：

1、最高位優先於最低位優先

假設有n個記錄的序列{R ₁ ，R ₂ ，...R _n }，且每個記錄R _i 中含有d個關鍵字(K _i ¹ ，K _i ² ，...，K _i ^d )，序列{R ₁ ，R ₂ ，...R _n }對關鍵字(K ¹ ，K ² ，...，K ^d )有序是指：對於序列中任意兩個記錄R _i 和R _j (1 <= i < j <= n)都滿足下列有序關系：(K _i ¹ ，K _i ² ，...，K _i ^d )<(K _j ¹ ，K _j ² ，...，K _j ^d )，其中K ¹ 稱為最高位關鍵字，K ^d 稱為最低位關鍵字。

實現多關鍵字排序的方法：
A、先對最高位關鍵字K ¹ 進行排序，間序列分成若乾子序列，每個子序列中的記錄都具有相同的K ¹ 值，然後分別對每個子序列對關鍵字K ² 進行排序，按K ² 值不同再分成若干更小的子序列，依次重復，直到對K ^d-1 進行排序後得到的每一子序列中的記錄都具有相同的關鍵字(K ¹ ，K ² ，...，K ^d-1 )，而後每個子序列分別對K ^d 進行排序，最後將所要子序列依次連接在一起成為一個有序序列，這種方法為「最高位優先(MSD)」
B、先從最低位關鍵字K ^d 進行排序，在對高一位的關鍵字K ^d-1 進行排序，依次重復，直至對K ¹ 進行排序後便成為一個有序序列。這種方法稱為「最低位優先(LSD)」。

三、內部排序方法的比較

結論：
1、表中的「簡單排序」指：除希爾排序外的所有插入排序，冒泡排序和簡單選擇排序，其中之間插入排序最簡單，當序列中的記錄「基本有序」或n值較小時，它是最佳的排序方法，因此常將他和其他排序方法（快排，歸並排序）結合在一起使用。
2、從平均時間性能看，快排最省時間，但他在最壞情況下的時間性能不如堆排序和歸並排序。在n較大，歸並排序所需時間比堆排序少，但所需的輔助存儲量最多。
3、基數排序適用於n值很大且關鍵字較小的序列。

❷ 歸並排序演算法是什麼

歸並排序（Merge Sort）是建立在歸並操作上的一種有效，穩定的排序演算法，該演算法是採用分治法（Divide and Conquer）的一個非常典型的應用。將已有序的子序列合並，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合並成一個有序表，稱為二路歸並。

歸並操作的工作原理如下：

第一步：申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合並後的序列。

第二步：設定兩個指針，最初位置分別為兩個已經排序序列的起始位置。

第三步：比較兩個指針所指向的元素，選擇相對小的元素放入到合並空間，並移動指針到下一位置。

重復步驟3直到某一指針超出序列尾。

將另一序列剩下的所有元素直接復制到合並序列尾。

❸ 分治演算法幾個經典例子

分治法，字面意思是「分而治之」，就是把一個復雜的1問題分成兩個或多個相同或相似的子問題，再把子問題分成更小的子問題直到最後子問題可以簡單地直接求解，原問題的解即子問題的解的合並，這個思想是很多高效演算法的基礎。

圖二

大整數乘法

Strassen矩陣乘法

棋盤覆蓋

合並排序

快速排序

線性時間選擇

最接近點對問題

循環賽日程表

漢諾塔

❹ 基於比較的排序演算法

    基於比較的排序演算法，應該是最符合人們直覺的方法。在各種演算法的技術書上，已經證明了基於比較的排序演算法的時間最優復雜度為O(nlogn)。

    下面是幾種常見的基於比較的排序演算法：

    1. 選擇排序：這應該是最直觀的排序方法。在排序n個元素時，第一次遍歷，找到最小的元素，將其與第一個元素互換；第二次遍歷，找到次小的元素，將其與第二個元素交換；直至剩下最後一個元素。

    2. 冒泡排序：這應該是我們學到的第一種排序演算法。基本思想就是，通過依次比較相鄰的兩個元素，如後值比前值小，則交換這兩個值，小值被交換到前面，大值被交換到後面。這樣一次遍歷後，最大值被放到最後。而小值被交換到n-1前。然後再次遍歷前n-1，n-2，直至最後2個元素。整個兒過程，小值隨著不斷的遍歷過程，逐漸被交換到前面，很像氣泡逐漸從水底逐漸冒出。所以被稱為冒泡演算法。

    3. 插入排序：這個演算法的思想很直觀。按照《演算法導論》中的解釋，這個演算法可以參照我們平時打撲克的情形。當抓取一張牌的時候，按順序比較手牌，將其插入到恰當的位置。這樣保證了手中所有的牌依然有序。當已排序的值數量較多時，由於已經保證了有序，那麼在確定新值插入位置的時候，可以通過二分查找的方法來去確定插入位置。

    4. 希爾排序：在冒泡演算法中，所以小值只能以步長為1的速度向前面移動。希爾排序在步長上作了優化，開始以一個較大的m步長進行分組，每組進行插入排序，這樣就實現了步長為m的移動。然後逐漸縮小步長m直至1。所以根本思想是盡可能的將元素移動較遠的位置代替移動一位。

5.歸並排序：該思想利用的是解決問題的一個常用思想，divide-and-conquer，即分而治之的思想。將n個元素每次2分，變為兩個n/2個元素組，直至1個元素——1個元素，自然是排好序了。然後，再兩兩合並元素組，最終合並為一個元素組。歸並演算法，因為需要歸並，所以必然需要一個額外的n空間來實現歸並。

    6.快速排序：同樣是分而治之的思想，將原始數據分為2組。但是與歸並演算法直接將原始數據分為兩部分不同的是，快排選擇一個中值，新的兩個子組，一個子組所有的元素都小於中值，另外一個子組所有的元素都大於等於中值，直至元素個數為1。當元素個數為1時，實際上快排已經完成了排序。這點與歸並排序也不同，快排在子組完成以後，無需額外的操作。很明顯，快排的效率依賴於中值的選擇。如果中值可以將數據分為兩個數量相等的子組，那麼效率則為最高的。快排無需額外的存儲空間，可以in-place進行排序。

    7.堆排序：該思想是將原始元素視為一個平衡二叉樹。然後要求父節點必須大於子節點的規則，調整該平衡二叉樹。由於是平衡二叉樹，所以數據被完美的等分。這樣根節點即為最大值。這時，堆排序完成了最大值的選擇。為排序，則將根節點與最後一個子節點交換。此時，樹的規則被破壞，需要從根節點逐級verify規則。