歸並是什麼演算法策略

1. 歸並排序演算法是什麼

歸並排序演算法定義如下：

歸並排序演算法就是利用分治思想將數組分成兩個小組A，B，再將A，B小組各自分成兩個小組，依次類推，直到分出來的小組只有一個數據時，可以認為這個小組已經是有序的了，然後再合並相鄰的二個小組就可以了。這樣通過先遞歸的分解數組，再合並數組，就完成了歸並排序。

歸並排序演算法特點：

由於歸並排序在歸並過程中需要與原始記錄序列同樣數量的存儲空間存放歸並結果以及遞歸時深度為log2n(2為底)的棧空間。

因此空間復雜度為O(n+logn)，Merge函數中if(SR[i] < SR[j])語句說明需要兩兩比較，不存在跳躍，因此歸並排序是一種穩定的排序演算法，歸並排序是一種比較佔用內存，但卻效率高且穩定的演算法。

2. 穩定的排序演算法有哪些

穩定的排序演算法：冒泡排序、插入排序、歸並排序、基數排序、計數排序。

1、冒泡排序：冒泡排序是一種基本的比較排序演算法，它通過多次遍歷數據來將較大的元素逐漸「冒泡」到數組的末尾。冒泡排序是穩定的，但在大型數據集上性能較差。

2、插入排序：插入排序是一種簡單的排序演算法，它逐個將元素插入已排序的部分。插入排序是穩定的，適用於小型數據集。

3、歸並排序：歸並排序採用分治策略，將數據分成小的部分，然後合並這些部分以獲得最終的有序數組。歸並排序是一種高效的排序演算法，而且是穩定的。

4、基數排序：基數排序是一種非比較排序演算法，它根據數字的位數來對數據進行排序。它是穩定的，特別適合對數字進行排序。

5、計數排序：計數排序是一種非比較排序演算法，它通過統計每個元素出現的次數來對數據進行排序。計數排序是穩定的，但對數據的范圍有一定要求。

不穩定的排序演算法

1、快速排序：快速排序是一種基於分治思想的排序演算法，通常通過選擇一個樞紐元素並將數據分成兩部分來實現排序。快速排序是不穩定的，因為在交換元素的過程中可能改變相等元素的相對順序。

2、堆排序：堆排序是一種基於二叉堆的排序演算法，它不保證相等元素的相對順序。在堆排序中，元素的交換可能導致相等元素之間的相對順序改變。

3、希爾排序：希爾排序是一種改進的插入排序演算法，它不保證相等元素的相對順序。希爾排序的排序過程中涉及增量，相等元素之間的相對位置可能發生變化。

4、選擇排序：選擇排序每次選擇最小（或最大）的元素並將其放在已排序部分的末尾。由於選擇排序的交換操作不是穩定的，它可能改變相等元素的相對順序。

5、希爾排序：希爾排序是一種改進的插入排序演算法，它不保證相等元素的相對順序。希爾排序的排序過程中涉及增量，相等元素之間的相對位置可能發生變化。

3. 歸並排序演算法是什麼

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

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

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

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

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

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

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

4. 數據結構--歸並排序與基數排序

一、歸並排序
歸並排序（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值很大且關鍵字較小的序列。