Python Merge Sort Algorithm Tutorial

了解如何在 Python 中實現歸併排序。分而治之排序策略的互動式逐步範例。

在編輯器中嘗試

概述

歸併排序是一種高效率的排序演算法，採用分而治之的策略。它將未排序的列表分解為較小的子列表，對這些子列表進行排序，然後將它們合併在一起。

此演算法遞歸地將數組分成兩半，直到達到單元素子數組。然後，它透過比較每一側的元素並將它們按排序順序放置，來合併排序的子數組。這確保了最佳的時間複雜度。

無論初始數組是排序的、反轉的還是完全隨機的，歸併排序都會在 O(n log n) 時間內執行。然而，在合併階段需要 O(n) 額外空間來保存子清單。

程式碼和執行輸出

Python 中合併排序演算法的標準遞歸實作。

merge_sort.py

在編輯器中嘗試

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
        
    mid = len(arr) // 2
    left_half = merge_sort(arr[:mid])
    right_half = merge_sort(arr[mid:])
    
    return merge(left_half, right_half)

def merge(left, right):
    result = []
    i = j = 0
    
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
            
    result.extend(left[i:])
    result.extend(right[j:])
    return result

# Test dataset
data = [38, 27, 43, 3, 9, 82, 10]
print("Original List:", data)
sorted_data = merge_sort(data)
print("Sorted List:  ", sorted_data)

端子輸出

Original List: [38, 27, 43, 3, 9, 82, 10]
Sorted List:   [3, 9, 10, 27, 38, 43, 82]

逐步實施

將鍊錶進行排序，其中節點結構便於輕鬆合併，無需複製
针对不完全适合系统 RAM 的文件的外部排序例程
稳定的排序应用程序，其中匹配键必须保留其原始顺序

常見問題解答

歸併排序是一種穩定的排序演算法嗎？

Yes, Merge Sort is stable. When comparing identical elements, the element from the left (original first) subarray is placed first, preserving their original relative positions.

為什麼Python使用Timsort而不是純粹的歸併排序？

Python 內建的「sorted()」使用 Timsort，這是一種結合了歸併排序和插入排序的混合演算法。它通过识别已经排序的子段来优化现实世界的数据模式，比纯粹的合并排序更快地呈现它。