归并排序原理及Python实现 - 分治法经典案例详解

什么是归并排序？

归并排序（Merge Sort）是一种采用分治法（Divide and Conquer）思想的排序算法。该算法将原始数组不断分割成更小的子数组，直到每个子数组只包含一个元素，然后逐步合并这些子数组，同时进行排序，最终得到一个完全有序的数组。

O(n log n)

时间复杂度

稳定

排序性质

O(n)

空间复杂度

归并排序的核心思想

归并排序基于以下三个关键步骤：

分解（Divide）：将当前数组分割成两个大小相等（或相差1）的子数组
解决（Conquer）：递归地对两个子数组进行排序
合并（Combine）：将两个已排序的子数组合并成一个有序数组

归并排序过程可视化

38 27 43 3 9 82 10

↓ 分解 ↓

左子数组

38 27 43 3

右子数组

9 82 10

↓ 递归排序 ↓

3 27 38 43

9 10 82

↓ 合并 ↓

3 9 10 27 38 43 82

归并排序的Python实现

下面是归并排序的完整Python实现代码，包含详细注释：

# 归并排序Python实现
def merge_sort(arr):
    """归并排序主函数"""
    if len(arr) <= 1:
        return arr
    
    # 分割数组
    mid = len(arr) // 2
    left_arr = arr[:mid]
    right_arr = arr[mid:]
    
    # 递归排序
    left_arr = merge_sort(left_arr)
    right_arr = merge_sort(right_arr)
    
    # 合并已排序的子数组
    return merge(left_arr, right_arr)

def merge(left, right):
    """合并两个已排序的数组"""
    merged = []
    left_index = 0
    right_index = 0
    
    # 比较左右数组元素，按顺序合并
    while left_index < len(left) and right_index < len(right):
        if left[left_index] < right[right_index]:
            merged.append(left[left_index])
            left_index += 1
        else:
            merged.append(right[right_index])
            right_index += 1
    
    # 添加剩余元素
    merged.extend(left[left_index:])
    merged.extend(right[right_index:])
    
    return merged

# 测试归并排序
if __name__ == "__main__":
    arr = [38, 27, 43, 3, 9, 82, 10]
    print("排序前:", arr)
    sorted_arr = merge_sort(arr)
    print("排序后:", sorted_arr)

代码说明：

merge_sort 函数：递归地将数组分成两半，直到每个子数组只有一个元素，然后调用merge函数合并子数组
merge 函数：合并两个已排序的子数组。通过比较两个子数组的元素，按顺序添加到新数组中
当其中一个子数组的元素全部添加后，将另一个子数组剩余元素直接添加到新数组末尾

归并排序的性能分析

时间复杂度

归并排序的时间复杂度在所有情况下都是 O(n log n)：

分解过程：O(log n) - 将数组不断二分
合并过程：O(n) - 每次合并需要线性时间
总时间复杂度：O(n) × O(log n) = O(n log n)

空间复杂度

归并排序需要额外的空间来存储临时数组：

每次合并操作都需要一个与原数组大小相同的临时数组
空间复杂度为 O(n)
不是原地排序算法

稳定性

归并排序是稳定的排序算法：

在合并过程中，当左右两个子数组的元素相等时，优先选择左子数组的元素
这保证了相等元素的原始相对顺序不变

归并排序原理及Python实现 - 分治法经典案例详解

归并排序算法原理与Python实现

什么是归并排序？

归并排序的核心思想