排序算法（四）：歸并排序

歸并排序是通過分治的方式，将待排序集合拆分為多個子集合，對子集合排序後，合并子集合成為較大的子集合，不斷合并最終完成整個集合的排序。

以下所講歸并都是指二路歸并：

之前的冒泡、選擇和插入排序都是維持一個待排序集合和一個已排序集合，在每次的疊代過程中從待排序集合中移動一個元素到已排序集合中，通過不斷的疊代來完成排序，是以需要進行的疊代次數一般都是

級别。而歸并排序則是每輪疊代消除半數的待排序子集合，是以需要進行的疊代次數為

級别。

算法過程

以遞增排序為例

1. 将集合盡量拆分為兩個元素個數相等的子集合，并對子集合繼續拆分，直到拆分後的子集合元素個數為 1；
2. 将相鄰子集合進行合并成為有序集合，若集合個數為奇數則最末尾集合不參與此次合并；
3. 重複步驟 2，直到集合個數為 1

合并操作

設有兩個已排序集合

和

，集合中元素個數分别為

，則合并

的操作為：

1. 聲明一個大小為

   

   的集合

   

   用于存放合并後元素；
2. 聲明

   

   

   兩個變量分别指向兩個集合中的首元素；
3. 比較

   

   

   指向的元素大小，将較小的元素存放到集合

   

   中，并更新變量指向下一個元素；
4. 重複步驟 3，直到

   

   

   中一個集合的元素已全部移動到集合

   

   中，則将另一個集合中未移動的元素全部添加到集合

   

   中

合并操作示例

merge

指向集合一中首元素位置，即指向元素 1 ，

指向集合二中首元素位置，即指向元素 3。比較 1 和 3 并将元素 1 存放到臨時集合中，更新

指向元素 5。比較 5 和 3 并将元素 3 存放到臨時集合中，更新

指向元素 7。再次比較并将元素 5 存放到臨時集合中，此時集合一中所有元素都放到了臨時集合中，則将集合二中剩餘所有元素添加到臨時集合中。

通過以上過程可以發現，若集合一和集合二中元素個數皆是

：

• 若集合一中最小元素，大于集合二中最大元素，則隻需要比較

  

  次即可
• 若兩集合中元素呈現交叉形式，如：[1, 3, 5]、[2, 4, 6]，則需要的比較次數為

  

合并操作代碼

def merge(arr, left, right, end):
    # 聲明index_1、index_2分别指向兩個集合的首元素位置
    # 聲明temp_arr_index指向臨時集合的首元素位置
    index_1, index_2, temp_arr_index = left, right, left
    # 比較兩集合元素，選擇較小的元素添加到臨時集合中
    while index_1 < right and index_2 <= end:
        if arr[index_1] <= arr[index_2]:
            temp_arr[temp_arr_index] = arr[index_1]
            index_1 = index_1 + 1
        else:
            temp_arr[temp_arr_index] = arr[index_2]
            index_2 = index_2 + 1
        temp_arr_index = temp_arr_index + 1
    # 集合1元素并未全部添加到臨時集合，則添加剩餘元素到臨時集合中
    while index_1 < right:
        temp_arr[temp_arr_index] = arr[index_1]
        index_1 = index_1 + 1
        temp_arr_index = temp_arr_index + 1
    # 集合2元素并未全部添加到臨時集合，則添加剩餘元素到臨時集合中
    while index_2 <= end:
        temp_arr[temp_arr_index] = arr[index_2]
        index_2 = index_2 + 1
        temp_arr_index = temp_arr_index + 1
    temp_arr_index = left
    # 将臨時集合中元素複制回arr集合中，即完成了兩個子集合的合并
    while temp_arr_index <= end:
        arr[temp_arr_index] = temp_arr[temp_arr_index]
        temp_arr_index = temp_arr_index + 1
           

算法過程示例

recursive merge sort

上圖中所示為使用遞歸方式完成歸并排序的過程。若集合隻有一個元素，則該集合為有序的，是以将原始集合拆分為多個隻有單個元素的子集合後，則每次合并選擇的兩個集合都是有序集合。然後将合并後的有序集合再進行合并，回溯執行，直到合并後的集合包含所有元素，即完成了排序。

算法遞歸代碼

def mergeSort(arr, left, right):
    if not right > left:
        return
    middle = left + (right - left) // 2
    mergeSort(arr, left, middle)   # 左半部分集合進行排序
    mergeSort(arr, middle + 1, right)   # 右半部分集合進行排序
    merge(arr, left, middle + 1, right)   #将左右子集合合并，即完成整個集合的排序
           

非遞歸實作

歸并排序的思路是通過不斷合并有序子集合來構成更大的有序集合，直到合并後的集合包含所有元素。

循環合并過程

non_recursive merge sort

在循環方式的歸并排序中，随着集合中元素個數的增多，不斷調整集合與下一個集合的間距來完成合并。

非遞歸代碼

def non_recursive_mergeSort(arr):
    global temp_arr   #臨時序列存儲空間
    temp_arr = [None] * len(arr)
    gap_len = 1  #集合之間的間距
    while gap_len < len(arr):
        left = 0
        while left + gap_len < len(arr): #判斷下一個集合是否存在
            right = left + gap_len
            if right + gap_len - 1 < len(arr):  #判斷下一個集合的尾元素位置
                end = right + gap_len - 1
            else:
                end = len(arr) - 1
            merge(arr,left,right,end)
            left = left + gap_len * 2
        gap_len = gap_len * 2
           

代碼分析 ：

• 第一層循環為判斷停止條件，即集合之間的間距不小于原始集合的長度時排序完成。因為集合的間距以指數形式增長，是以元素個數為

  

  的集合，疊代的次數為

  

  級别；
• 嵌套循環作用是周遊合并相鄰的兩個子集合。

算法分析

歸并排序是一種穩定排序算法，排序過程中，如果兩個元素值相等，則不交換元素位置。對于

個元素的序列：

• 最壞情況下，當每兩個待合并集合的元素大小呈現交叉形式時，需要比較的次數為兩集合元素個數之和減一。即

  

  個元素的集合，共需要比較的次數最多為：

  

  ，公式中的每一項，括号中表示兩個集合合并需要進行的比較次數，即元素個數之和減一。括号後乘的系數為拆分後每一層有多少組集合。即最壞情況下的比較次數為：

  

• 最好情況下，當待合并的兩個集合中，其中一個集合的最小元素大于另一個集合的最大元素時，需要比較的次數為其中一個集合的元素個數。即

  

  

  ，即最好情況下的比較次數為：

  

無論是最好情況或者最壞情況下，每兩個集合的合并操作都需要移動全部元素到臨時集合中，再從臨時集合中移動回原集合中，是以歸并排序中元素的移動次數為：

。根據算法執行的比較次數和元素移動次數可知，算法的時間複雜度為：

。算法執行過程中，需要申請額外的序列空間來儲存臨時元素，是以算法的空間複雜度為

。

github

連結： 歸并排序