Python归并排序详解（手把手教你掌握分治思想的高效排序算法）

为什么选择归并排序？

相比冒泡排序、选择排序等 O(n²) 算法，归并排序算法具有以下优势：

• 时间复杂度稳定为 O(n log n)，无论最好、最坏还是平均情况。
• 是稳定的排序算法（相等元素的相对位置不会改变）。
• 适合处理大规模数据，尤其适用于外部排序（如磁盘文件排序）。

Python归并排序完整实现

下面是一个清晰、注释完整的 Python排序教程 代码示例：

# 归并排序主函数def merge_sort(arr):    # 基线条件：如果数组长度小于等于1，直接返回    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):    sorted_list = []    i = j = 0    # 比较左右两个列表的元素，按顺序合并    while i < len(left) and j < len(right):        if left[i] <= right[j]:            sorted_list.append(left[i])            i += 1        else:            sorted_list.append(right[j])            j += 1    # 将剩余元素添加到结果列表中    sorted_list.extend(left[i:])    sorted_list.extend(right[j:])    return sorted_list# 测试示例if __name__ == "__main__":    data = [38, 27, 43, 3, 9, 82, 10]    print("原始数组:", data)    sorted_data = merge_sort(data)    print("排序后数组:", sorted_data)  

代码解析

上述代码分为两个核心函数：

1. merge_sort()：递归地将数组一分为二，直到子数组长度为1。
2. merge()：将两个已排序的小数组合并成一个大数组。

这种“先分后合”的策略正是分治算法Python实现的典型范例。

时间与空间复杂度

• 时间复杂度：O(n log n) —— 每次分割为 log n 层，每层合并需 O(n) 时间。
• 空间复杂度：O(n) —— 需要额外的临时数组存储合并结果。

总结

通过本篇Python归并排序教程，你应该已经掌握了这一经典排序算法的核心思想与实现方式。归并排序不仅是面试常客，更是理解递归与分治思想的绝佳入门案例。建议你动手运行代码、修改测试数据，加深理解。

记住：编程不是看会的，而是练会的！