如何用Python實現歸併排序

歸併排序是一種經典的排序演算法，其核心思想是將待排序數組分成若干個子數組，對這些子數組進行排序，最後再將排好序的子數組合併成一個有序數組。歸併排序是一種效率較高的排序演算法，其時間複雜度為O(nlogn)。

在本文中，我們將講解如何用Python實作歸併排序。

1. 實作歸併排序的想法

歸併排序的實作想法包含兩個部分，分別是分治與合併。具體實作步驟如下：

1）將待排序數組不斷一分為二，遞歸地將左右兩部分排序；

2）將排好序的左右兩部分合併成一個有序數組。

2. 用Python實現分治

分治是歸併排序的核心思想，我們需要先實現分治的部分。

程式碼如下：

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

在這個函數中，我們先判斷如果陣列長度小於等於1，則直接傳回該陣列。否則，我們需要將該數組一分為二，分別對左右兩部分進行遞歸排序，最後再將排好序的左右兩部分合併起來。

2.1 實作合併

在實現分治的基礎上，我們需要實作合併的部分。

程式碼如下：

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

在這個函數中，我們先初始化指標i和j，分別指向左右兩部分要比較的元素。接著我們不斷比較左右兩部分元素，將較小的元素加入結果清單中，並將該指標右移。最後，我們也要將剩下的所有元素加入到結果清單中，以便最終得到排好序的陣列。

3. 完整程式碼

將分治與合併部分組合起來，得到完整程式碼如下：

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

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

##測試

為了驗證我們的歸併排序程式碼是否正確，我們需要進行測試。

程式碼如下：

arr = [5, 3, 8, 6, 4, 7, 2, 1]
print(merge_sort(arr))

輸出結果為：

[1, 2, 3, 4, 5, 6, 7, 8]

#測試結果表明，我們的歸併排序代碼是正確的。

以上是如何用Python實現歸併排序的詳細內容。更多資訊請關注PHP中文網其他相關文章！