算法入門——插入排序和歸并排序

新手算法入門，萌新一枚，如有錯誤，請多見諒！内容主要來源于《算法導論》。
           

插入排序

插入排序，主要适用于少量元素的排序，就像打撲克一樣，左手拿已經排好的牌組，右手從待排序的牌堆中拿取一張，從右往左依次比較，找到合适位置時停下，插入，此牌右邊的牌在排序過程中順次右移一位。算法複雜度為Θ( n 2 n^2 n2)。

僞代碼如下（将 A 數組遞增輸出）：

INSERTION-SORT(A):
     for j = 2 to A.length:
         key = A[j]
         //Insert the A[j] into the sorted A[1..j-1]
         i = j - 1
         while i >0 and A[j] > key 
             A[i+1] = A[i]
             i = i -1
         A[i] = A[j]
  
           

歸并排序

适用于規模較大的排序問題算法複雜度為Θ( n ∗ l o g 2 n n*log_2{n} n∗log2​n)

歸并算法遵循分治法，在算法結構上是遞歸的，遵循3個步驟

1. 分解：原問題分為若幹子問題，這些問題是原問題的規模較小的執行個體。
2. 解決：這些子問題，遞歸地求解各子問題。然而，各子問題的規模較小，可以直接求解。
3. 合并：合并兩個已排序的子序列以産生已排序的答案。

歸并算法完全遵循分治法，

1. 分解：分解待排序的n個元素的序列成各具n/2個元素的兩個子序列。
2. 解決：使用歸并排序遞歸地排序兩個子序列。
3. 合并：合并兩個已排序好的子序列以産生已排序好的答案。

歸并算法的關鍵在于‘合并’步驟中合并兩個已排序好的子序列以産生已排序好的答案。通過調用一個輔助過程MERGE(A,p,q,r)完成合并，其中A是一個數組，A[p,q]和A[q+1,r]已經完成排序，它合并這兩個數組形成一個單一的已排好序的子數組來代替A[p,r]

同樣以打撲克為例，假設桌面有兩堆已經排好序牌面朝上的牌，面朝上，最小的牌在頂上。我們希望将這兩堆牌合并成單一的排好序的輸出堆，牌面朝下地放在桌上。

我們的基本步驟包括在牌面朝上的兩堆牌的頂上兩張牌選取最小的一張，将該牌從其堆中移開（該堆的頂上将露出一張新牌），并牌面朝下地放在輸出堆中。重複這個步驟，直到一個輸入堆為空。這時我們隻需将另一堆牌面朝下地放置到輸出堆中。

由于需要判定輸入堆何時為空，是以我們在每個堆底部放置一張哨兵牌，因為遞增輸出，将 ∞ ∞ ∞最為哨兵值,則不可能有比哨兵牌更大的牌，由于程式共進行(r-p+1)次抽牌,哨兵牌不會被抽中。

以下是合并操作的代碼：`MERGE(A,p,q,r)

MERGE(A,p,q,r)
    n1 = q - p + 1
    n2 = r - q
    let L[1,n1 + 1] and R[1,n2 + 1] be new arrays
    for i = 1 to n1
        L[i] = A[p + i - 1]
    for j = 1 to n2
        R[j] = A[q + i]
    L[i + 1] = ∞
    R[j + 1] = ∞
    i = 1
    j = 1
    for k = p to r
        if L[i] <= R[j]
            A[k] = L[i]
            i = i + 1
        else 
            A[k] = R[j]
            j = j + 1
            

           

現在我們可以将過程MERGE(A,p,q,r)作為歸并算法的子程式使用。若p>=r,則該子數組中最多有一個元素是以已經排好序。否則分解步驟簡單地計算一個下标q,将A[p…r]簡單地分解為兩個子數組A[p…q]和A[q+1…r]

下面是歸并算法MERGE-SORT(A,p,r)的僞代碼：

MERGE-SORT(A,p,r)
if p < r
    q = [(p+r)/2]
    MERGE-SORT(A,p,q)
    MERGE-SORT(A,q+1,r)
    MERGE(A,p,q,r)