歸併排序的基本思想¶
歸併排序是一種基於分治法（Divide and Conquer）的高效排序算法。它的核心思路可以概括爲三個步驟：分解（Divide）、遞歸排序（Conquer） 和 合併（Merge）。
- 分解：將待排序的數組從中間分成左右兩部分，直到每個子數組只包含一個元素（此時子數組本身就是有序的）。
- 遞歸排序：對左右兩個子數組分別遞歸執行歸併排序，直到所有子數組都有序。
- 合併：將兩個已排序的子數組合併成一個更大的有序數組，最終得到整個數組的排序結果。
簡單來說，歸併排序就是先把大問題拆分成小問題，解決小問題後再把結果合併起來。
分解過程詳解¶
假設我們有一個數組 [3, 1, 4, 2]，歸併排序的分解過程如下：
- 第一次分解：數組長度爲4，中間位置是
4//2=2，所以分成左右兩部分：left = [3, 1]和right = [4, 2]。 - 遞歸分解左子數組
[3, 1]：中間位置是2//2=1，分成left_left = [3]和left_right = [1]（每個子數組長度爲1，無需再分解）。 - 遞歸分解右子數組
[4, 2]：中間位置是2//2=1，分成right_left = [4]和right_right = [2]（每個子數組長度爲1，無需再分解）。
遞歸排序與合併¶
當分解到子數組長度爲1時，子數組已經有序（單個元素本身就是有序的）。此時需要執行合併操作，將兩個有序子數組合併成一個更大的有序數組。
以分解後的子數組爲例：
- 左子數組合並：[3] 和 [1] 合併成 [1, 3]。
- 右子數組合並：[4] 和 [2] 合併成 [2, 4]。
- 最終合併：[1, 3] 和 [2, 4] 合併成 [1, 2, 3, 4]。
Python代碼實現¶
下面是歸併排序的Python實現，分爲合併函數和遞歸排序函數兩部分：
1. 合併函數 merge(left, right)¶
功能：合併兩個已排序的子數組，返回一個新的有序數組。
def merge(left, right):
merged = [] # 存儲合併後的結果
i = j = 0 # 兩個子數組的指針（索引）
# 比較兩個子數組的元素，按順序加入merged
while i < len(left) and j < len(right):
if left[i] <= right[j]:
merged.append(left[i])
i += 1
else:
merged.append(right[j])
j += 1
# 將剩餘未比較的元素直接加入（可能其中一個子數組已遍歷完）
merged.extend(left[i:]) # 添加left中剩餘元素
merged.extend(right[j:]) # 添加right中剩餘元素
return merged
2. 遞歸排序函數 merge_sort(arr)¶
功能：遞歸分解數組，調用合併函數得到排序結果。
def merge_sort(arr):
# 基本情況：數組長度爲1或0時，本身就是有序的
if len(arr) <= 1:
return arr
# 分解數組：分成左右兩部分
mid = len(arr) // 2
left = merge_sort(arr[:mid]) # 遞歸排序左半部分
right = merge_sort(arr[mid:]) # 遞歸排序右半部分
# 合併兩個已排序的子數組
return merge(left, right)
測試代碼¶
if __name__ == "__main__":
test_array = [3, 1, 4, 2, 5]
sorted_array = merge_sort(test_array)
print("原始數組:", test_array)
print("排序後數組:", sorted_array)
輸出結果：
原始數組: [3, 1, 4, 2, 5]
排序後數組: [1, 2, 3, 4, 5]
歸併排序的特點¶
- 時間複雜度：無論輸入數組如何，歸併排序的時間複雜度始終爲 O(n log n)（分解和合並的總操作次數爲O(n log n)）。
- 空間複雜度：需要額外的數組存儲合併結果，空間複雜度爲 O(n)。
- 穩定性：歸併排序是穩定的排序算法（相等元素的相對順序保持不變）。
歸併排序的核心是“分而治之”和“合併有序數組”，通過遞歸分解和合並，最終實現整個數組的排序。雖然代碼看起來比冒泡排序等簡單排序算法複雜，但理解其思路後，會發現它非常直觀且高效。