Python中怎么實現歸并排序

Python中怎么實現歸并排序

歸并排序（Merge Sort）是一種高效的排序算法，采用分治法（Divide and Conquer）的思想。它將一個數組分成兩個子數組，分別對這兩個子數組進行排序，然后將排序后的子數組合并成一個有序的數組。歸并排序的時間復雜度為O(n log n)，是一種穩定的排序算法。

歸并排序的基本思想

歸并排序的核心思想是“分而治之”，具體步驟如下：

1. 分解：將待排序的數組遞歸地分成兩個子數組，直到每個子數組只包含一個元素。
2. 合并：將兩個有序的子數組合并成一個有序的數組。

通過不斷地分解和合并，最終得到一個完全有序的數組。

歸并排序的實現

下面我們來看如何在Python中實現歸并排序。

1. 分解

首先，我們需要將數組遞歸地分成兩個子數組。這個過程可以通過遞歸來實現。

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    
    # 找到中間點，將數組分成兩部分
    mid = len(arr) // 2
    left_half = arr[:mid]
    right_half = arr[mid:]
    
    # 遞歸地對左右兩部分進行排序
    left_half = merge_sort(left_half)
    right_half = merge_sort(right_half)
    
    # 合并兩個有序的子數組
    return merge(left_half, right_half)

2. 合并

接下來，我們需要實現合并兩個有序子數組的函數。合并的過程如下：

1. 創建一個臨時數組，用于存儲合并后的結果。
2. 使用兩個指針分別指向兩個子數組的起始位置。
3. 比較兩個指針所指的元素，將較小的元素放入臨時數組，并移動相應的指針。
4. 重復步驟3，直到其中一個子數組的所有元素都被放入臨時數組。
5. 將另一個子數組中剩余的元素放入臨時數組。

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

3. 完整代碼

將上述兩個函數結合起來，我們就可以得到一個完整的歸并排序實現：

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    
    mid = len(arr) // 2
    left_half = arr[:mid]
    right_half = arr[mid:]
    
    left_half = merge_sort(left_half)
    right_half = merge_sort(right_half)
    
    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

# 測試
arr = [38, 27, 43, 3, 9, 82, 10]
sorted_arr = merge_sort(arr)
print("排序后的數組:", sorted_arr)

4. 運行結果

運行上述代碼，輸出結果為：

排序后的數組: [3, 9, 10, 27, 38, 43, 82]

歸并排序的復雜度分析

• 時間復雜度：歸并排序的時間復雜度為O(n log n)。這是因為每次分解數組都需要O(log n)的時間，而每次合并兩個子數組需要O(n)的時間。
• 空間復雜度：歸并排序的空間復雜度為O(n)，因為需要額外的空間來存儲合并后的數組。

總結

歸并排序是一種高效且穩定的排序算法，適用于大規模數據的排序。通過分治法的思想，歸并排序能夠將復雜的問題分解成簡單的子問題，并通過遞歸和合并的方式解決。在Python中，歸并排序的實現相對簡單，代碼清晰易懂。希望本文能幫助你理解并掌握歸并排序的實現方法。