文章目录
- 一、原理
- 二、步骤
- 三、时间复杂度
- 四、空间复杂度
- 五、可视化过程
- 六、示例代码
- 七、适用场景
- 八、不适用场景
- 九、相关文章
一、原理
归并排序是一种分治算法（Divide and Conquer），其核心思想是： 分解：将数组递归地分成两半，直到每个子数组只有一个元素（此时默认有序）。 合并：将两个已排序的子数组合并成一个有序数组，直到最终合并完成整个数组。
特点：采用分治思想，递归拆分后合并有序子序列。
名称来源于其核心操作 “归并”（Merge），即合并两个有序序列。
二、步骤
- 分解：
- 合并：
三、时间复杂度
- 所有情况（最好、最坏、平均）：O(n log n)。 分解：每次递归将数组分成两半，共需 log n 层。 合并：每层需要遍历所有元素（n次操作）。
四、空间复杂度
O(n)（需额外空间存储临时数组）。
五、可视化过程
初始数组：[12, 11, 13, 5, 6, 7]
分解阶段：
1. [12, 11, 13, 5, 6, 7] → 分为 [12, 11, 13] 和 [5, 6, 7]
2. [12, 11, 13] → 分为 [12] 和 [11, 13]，[11, 13] → 分为 [11] 和 [13]
3. [5, 6, 7] → 分为 [5] 和 [6, 7]，[6, 7] → 分为 [6] 和 [7]
合并阶段：
1. 合并 [11] 和 [13] → [11, 13]
2. 合并 [12] 和 [11, 13] → [11, 12, 13]
3. 合并 [6] 和 [7] → [6, 7]
4. 合并 [5] 和 [6, 7] → [5, 6, 7]
5. 合并 [11, 12, 13] 和 [5, 6, 7] → [5, 6, 7, 11, 12, 13]
最终结果：[5, 6, 7, 11, 12, 13]
六、示例代码
def merge_sort(arr):
if len(arr) <= 1:
return arr
# 分解
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
# 合并
return merge(left, right)
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
# 测试示例
if __name__ == "__main__":
data = [12, 11, 13, 5, 6, 7]
print("排序前:", data)
sorted_data = merge_sort(data.copy())
print("排序后:", sorted_data)
排序前: [12, 11, 13, 5, 6, 7]
排序后: [5, 6, 7, 11, 12, 13]
七、适用场景
- 大规模数据排序：时间复杂度稳定为 O(n log n)，适合处理大量数据。
- 外部排序：常用于处理无法一次性装入内存的大型数据集。
- 稳定排序需求：归并排序是稳定的排序算法，适合需要保持相同元素相对顺序的场景。
- 链表排序：特别适合链表数据结构，因为不需要随机访问元素。
- 并行计算：分治特性使其容易实现并行化处理。
八、不适用场景
- 内存受限的环境，因为需要 O(n) 的额外空间。
- 数据量极小而简单排序更合适的场景。
- 对空间复杂度要求严格的嵌入式系统。
九、相关文章
Python冒泡排序原理与示例 Python选择排序原理与示例 Python插入排序原理与示例 Python堆排序原理与示 Python归并排序原理与示例（当前） Python希尔排序原理与示例 Python快速排序原理与示例
