算法漫遊指北(第十一篇):歸併排序算法描述、動圖演示、代碼實現、過程分析、複雜度

一、歸併排序

歸併排序是建立在歸併操作上的一種有效的排序算法。該算法是採用分治法(Divide and Conquer)的一個非常典型的應用。將已有序的子序列合併,得到完全有序的序列;即先使每個子序列有序,再使子序列段間有序。若將兩個有序表合併成一個有序表,稱為2-路歸併。

  • 所謂“分”,指的是將一個亂序數列不斷進行二分,得到許多短的序列。

  • 所謂“治”,指的是將這些短序列進行兩兩合併,然後將合併的結果作為新的序列,再與其他序列進行合併,最終得到一個新的序列。

歸併排序算法描述

 

  • 把長度為n的輸入序列分成兩個長度為n/2的子序列;

  • 對這兩個子序列分別採用歸併排序;

  • 將兩個排序好的子序列合併成一個最終的排序序列。

 

歸併排序動圖演示

 

動畫演示圖2

 

 

歸併排序代碼實現

def merge_sort(alist):
    """歸併排序"""
    n = len(alist)
    #遞歸結束條件
    # 剩一個或沒有直接返回,不用排序
    if n <= 1:
        return alist
    # 拆分
    mid = n//2
​
    # left 採用歸併排序后形成的有序的新的列表
    left_li = merge_sort(alist[:mid])
​
    # right 採用歸併排序后形成的有序的新的列表
    right_li = merge_sort(alist[mid:])
​
    # 將兩個有序的子序列合併為一個新的整體
    # merge(left, right)
    left_pointer, right_pointer = 0, 0
    result = []
​
    while left_pointer < len(left_li) and right_pointer < len(right_li):
        if left_li[left_pointer] <=  right_li[right_pointer]:
            result.append(left_li[left_pointer])
            left_pointer += 1
        else:
            result.append(right_li[right_pointer])
            right_pointer += 1
    
    #將兩個列表按順序融合為一個列表result
    result += left_li[left_pointer:]
    result += right_li[right_pointer:]
    return result
​

  


歸併排序過程分析

示例 針對 arrli = [6,5,3,1,8,7,2,4]進行歸併排序

1、拆分數組

假設數組一共有 n 個元素,我們遞歸對數組進行折半拆分即n//2,直到每組只有一個元素為止。

 

2、合併數組

算法會從最小數組開始有序合併,這樣合併出來的數組一直是有序的,所以合併兩個有序數組是歸併算法的核心,這裏用兩個簡單數組示例:

步驟1:新建一個空數組存放合併結果,用left_pointerright_pointer兩個輔助指針記錄兩個數組當前操作位置;

 

步驟2:從左到右逐一比較兩個小數組中的元素,較小的元素先放入新數組,指針移位,直到left_pointerright_pointer指針超出尾部;

 

步驟3:新建一個空數組存放合併結果,用lr兩個輔助指針記錄兩個數組當前操作位置;

 

步驟4:從左到右逐一比較兩個小數組中的元素,較小的元素先放入新數組,指針移位,直到lr指針超出尾部;

 

繼續比較寫入較小的元素到新數組

繼續比較寫入較小的元素到新數組

 

指針尚未移到尾部的數組,說明還有剩餘元素,將剩餘元素合併到新數組尾部。

 

步驟5:新建一個空數組存放合併結果,用lr兩個輔助指針記錄兩個數組當前操作位置;

 

步驟6:從左到右逐一比較兩個小數組中的元素,較小的元素先放入新數組,指針移位,直到lr指針超出尾部;

 

將較小的元素寫入到新數組

繼續比較寫入較小的元素到新數組

繼續比較寫入較小的元素到新數組

繼續比較寫入較小的元素到新數組

 

步驟7:右邊的指針尚未移到尾部的數組,說明還有剩餘元素,將剩餘元素合併到新數組尾部。

 

完成歸併排序,返回排好序的新數組

 

 

歸併排序複雜度

 

  • 時間複雜度:O(nlogn)

歸併排序把數組一層層折半分組,長度為 n 的數組,折半層數就是 logn,每一層進行操作的運算量是 n,得出時間複雜度 O(nlogn)。

  • 空間複雜度:O(n)

每次歸併操作需要創建額外的新數組,佔用空間為 n,但這部分額外空間會隨着方法的結束而釋放,所以只需要算單次歸併操作開闢的空間即可,得出空間複雜度 O(n)。

  • 穩定性:穩定

從算法中從左到右逐一比較,較小的先放入新數組,所以兩個值相同的元素,排序后依然保持原先後順序。

 

 

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※別再煩惱如何寫文案,掌握八大原則!

網頁設計一頭霧水該從何著手呢? 台北網頁設計公司幫您輕鬆架站!

※超省錢租車方案

※教你寫出一流的銷售文案?

網頁設計最專業,超強功能平台可客製化