Python 合併排序教學

排序數據是數據從業者在日常工作中最常見的操作之一。許多時候，我們需要以特定的順序顯示數據以提取有意義的信息。幸運的是，如今我們不必手動執行這項任務。計算機可以以無與倫比的性能為我們完成這個魔法。

有幾種策略可以用來排序數據。在本教程中，我們將分析一種最有效的排序技術。“合併排序”算法使用分治策略通過首先將未排序的數組拆分為更小的數組，然後按正確的順序合併它們來進行排序。

在接下來的部分中，我們將討論合併排序算法的所有細節，它在 Python 中的表現，以及一些平滑實現的實用技巧。

什麼是合併排序？

有許多排序算法，但很難找到一個性能優於合併排序的算法。毫不奇怪，這種算法被用於各種現實世界的應用中，例如排序大型數據庫或在普通計算機上組織文件。

該算法基於分治範式，可以分為三個部分：

• 分割：這個過程將問題分割成更小的子問題。
• 解決：子問題通過遞歸方式解決。
• 合併：將子問題的解決方案合併以達到最終解決方案。

分治策略

讓我們看看如何運作合併排序。假設我們想要使用合併排序演算法來排序以下數字。該演算法會將數據遞迴地分成兩部分，並持續分割直到每個列表只有一個元素。然後，我們將它們組合起來，通過將它們排序到另一個列表中。

合併排序問題。來源：DataCamp

合併排序的時間和空間複雜度

事先無法知道哪種排序演算法最適合某個問題。除了演算法外，還需要考慮其他變數，包括用於編寫代碼的編程語言、執行代碼的硬體以及要排序的數據的特點。

雖然我們無法預測排序演算法的確切運行時間，但我們仍然可以通過分析時間和空間複雜度來比較各種排序演算法的性能。

合併排序的時間複雜度

正如我們在關於大O符號和時間複雜度的另一個指南中所解釋的，時間複雜度分析的目標並不是預測算法的確切運行時間，而是通過分析輸入數據量增加時運行時間如何變化來評估算法的效率。

時間複雜度分析是用大O符號來表示的，這是一種描述函數增長或下降速度的數學表示法。合併排序具有對數線性或線性對數時間複雜度，表示為O(N log(N))，其中N是列表中的元素數量。字母’O’代表’增長的順序’。

在時間複雜度分析中，線性對數複雜度的行為與線性複雜度大致相似，這意味著其執行將直接與數據量成比例。因此，如果數據量加倍，算法處理數據所需的時間也應加倍，即劃分和合併的次數將加倍。

由於合併排序的時間複雜度是線性的，因此對於最佳、平均和最壞情況，其複雜度保持不變。這意味著無論輸入順序如何，該算法完成任務所需的步驟數始終保持不變。

合併排序的空間複雜度

最後，在分析算法複雜度時，除了完成任務所需的時間之外，另一個重要方面是估計隨著問題變得更大，算法完成任務將需要多少內存。

這涉及到空間複雜度和輔助空間的概念。後者是指算法使用的額外空間或臨時空間，而前者是指算法相對於輸入大小所佔用的總空間。換句話說，空間複雜度包括輔助空間和輸入所使用的空間。

合併排序的空間複雜度為 O(N)。這是因為它使用了一個大小為 N 的輔助數組來合併輸入數組的已排序部分。輔助數組用來存儲合併的結果，而輸入數組則被已排序的結果覆蓋。

Python 中的合併排序實現

讓我們在 Python 中實現合併排序算法。編寫算法有幾種方法；然而，我們將堅持使用基於遞歸的方法，這無疑是最容易理解的，並且所需的代碼行數少於其他基於迭代的替代方案。

理解合併排序中的遞歸

如果你對這個主題不熟悉，在編程中，遞歸是指一個函數調用自身。你可以查看我們的 理解 Python 中的遞歸函數教程 以了解這些強大的函數。

要實現合併排序，首先我們定義基本情況：如果列表只有一個元素，則它已經排序，因此我們立即返回。否則，我們將列表分成兩半，left_half 和 right_half，並在每個上面遞歸調用 merge_sort()。這個過程一直持續到所有子列表都包含單個元素。

一旦我們有了這些排序好的子列表，我們開始合併過程。為此，我們初始化三個索引變量：i 用於跟踪 left_half 中的位置，j 用於 right_half，以及 k 用於最終合併的列表。然後我們比較來自兩半的元素。如果 left_half 中的當前元素較小，我們將其放入 my_list[k] 並移動 i。否則，我們從 right_half 中取元素，將其放入 my_list[k]，並增加 j。每次比較後，我們將k向前移動到最終列表中的下一個位置。

這個過程一直持續到我們比較了其中一半的所有元素。如果 left_half 或 right_half 中還有任何元素剩餘，我們將它們直接附加到最終列表中，確保沒有數據被遺漏。由於合併排序是遞歸操作，這個合併過程在每個遞歸級別都執行，直到整個列表排序完成。

Python 實現

下面，您可以找到使用上一個圖表中未排序列表的代碼示例：

def merge_sort(my_list):
    if len(my_list) > 1: 
        mid = len(my_list)//2
        left_half = my_list[:mid]
        right_half = my_list[mid:]
       
        merge_sort(left_half)
        merge_sort(right_half)

        i = j = k = 0
 
        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                my_list[k] = left_half[i]                
                i += 1
            else:
                my_list[k] = right_half[j]
                j += 1
            k += 1
     
        while i < len(left_half):
            my_list[k] = left_half[i]
            i += 1
            k += 1
 
        while j < len(right_half):
            my_list[k] = right_half[j]
            j += 1
            k += 1

my_list = [35,22,90,4,50,20,30,40,1]
merge_sort(my_list)
print(my_list)
>>> [1, 4, 20, 22, 30, 35, 40, 50, 90]

Merge Sort與其他排序算法的比較

Merge Sort是一種非常快速的排序算法，特別適合用於大型數據庫，通常被用作其他算法的基準。然而，當涉及較短的列表時，其性能往往低於其他排序算法。

在下表中，您可以找到Merge Sort與其他流行排序算法的比較。

合併排序的實際應用

合併排序在排序大型列表時表現出色，但在處理較小列表時效率會降低。同樣，在輸入列表中已有一定程度的順序時，它也不太有效率，因為合併排序將執行相同的步驟，無論列表的順序如何。

合併排序特別適合於鏈表這樣的情況。鏈表是一種數據結構，包含線性連接在一起的節點。每個節點包含數據和與下一個節點連接的鏈接。

合併排序適用於鏈表，因為它只需要按順序訪問數據，這與鏈表的性質相符。此外，合併排序是一種穩定的排序算法（即在排序輸出中保持相等元素的相對順序），這在維護鏈表的順序時非常重要。

常見錯誤和疑難排解

合併排序算法非常直觀，代碼改進的空間有限。但是，您可以通過考慮輸入數據的大小來提高排序策略的複雜性。

我們已經確定合併排序在處理更大數據集時效果更好。對於較小的數據集，具有O(N^2)時間復雜度的其他排序算法，如插入排序，可能更有效。在這種情況下，您只需要創建一個大小閾值，低於該閾值時使用插入排序算法，而不是合併排序。

除此之外，探索的另一个好主意是并行化。借助正确的计算能力，合并排序的步骤可以很容易地并行化，从而缩短完成时间。阅读我们的CPU vs GPU 指南以了解更多关于并行计算的信息。

结论

合并排序是其中一种最有效和流行的排序算法，但在算法的精彩且不断扩展的宇宙中，还有许多值得学习的内容。如果您对算法的技术细节、工作原理以及它们的复杂性、优点和缺点感兴趣，这些 DataCamp 资源可以帮助您继续学习：

• 数据结构与算法课程
• Python 编程技能学习路线
• Python 数据基础技能学习路线
• 中级 Python 课程
• Python 数据分析师职业路线
• 大O標記法與時間複雜度