上一篇
归并排序算法原理
归并排序（Merge Sort）是一种基于分治思想的高效排序算法，由约翰·冯·诺伊曼于1945年发明。它的核心思想是将一个大问题分解为若干个小问题，分别解决后再合并结果。
归并排序的三个关键步骤：
1
分割（Divide）：将未排序的列表递归地分成两个子列表，直到每个子列表只包含一个元素（此时可以认为已排序）。
2
排序（Conquer）：递归地对子列表进行排序（当子列表长度为1时，自然有序）。
3
合并（Combine）：将两个已排序的子列表合并成一个新的有序列表。
归并排序可视化
38
27
43
3
9
82
10
归并排序特点
✅ 优点
- 时间复杂度稳定为 O(n log n)，在所有情况下都高效
- 稳定排序算法（相同元素的相对位置不变）
- 适合处理大数据集和外部排序
- 可以轻松实现并行化处理
⚠️ 缺点
- 需要额外的存储空间（O(n)空间复杂度）
- 对于小数据集可能不如插入排序等简单算法高效
- 递归实现可能导致调用栈过深的问题
Python实现归并排序
下面是归并排序的Python实现代码，包含详细注释：
归并排序Python实现
def merge_sort(arr):
"""
归并排序主函数
:param arr: 待排序的列表
:return: 排序后的列表
"""
# 递归结束条件：数组长度小于等于1
if len(arr) <= 1:
return arr
# 分割步骤：找到中间点并分割数组
mid = len(arr) // 2
left_half = arr[:mid]
right_half = arr[mid:]
# 递归调用：对左右子数组进行排序
left_half = merge_sort(left_half)
right_half = merge_sort(right_half)
# 合并排序后的左右子数组
return merge(left_half, right_half)
def merge(left, right):
"""
合并两个已排序的数组
:param left: 左数组
:param right: 右数组
:return: 合并后的有序数组
"""
merged = []
left_index = 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
# 将剩余元素添加到结果数组中
# 左数组还有剩余元素
while left_index < len(left):
merged.append(left[left_index])
left_index += 1
# 右数组还有剩余元素
while right_index < len(right):
merged.append(right[right_index])
right_index += 1
return merged
# 测试归并排序
if __name__ == "__main__":
example_arr = [38, 27, 43, 3, 9, 82, 10]
print("原始数组:", example_arr)
sorted_arr = merge_sort(example_arr)
print("排序后数组:", sorted_arr)代码说明
merge_sort 函数：
- 检查数组长度，如果长度≤1则直接返回（递归终止条件）
- 计算中点位置，将数组分成左右两部分
- 递归调用merge_sort对左右子数组排序
- 调用merge函数合并两个已排序的子数组
merge 函数：
- 初始化两个指针(left_index, right_index)和结果数组
- 比较两个子数组当前指针位置的元素，将较小的元素加入结果数组
- 当其中一个子数组遍历完后，将另一个子数组剩余元素全部加入结果数组
时间复杂度分析
| 情况 | 时间复杂度 | 说明 |
|---|---|---|
| 最佳情况 | O(n log n) | 所有分割和合并操作都需要log n层，每层O(n)操作 |
| 平均情况 | O(n log n) | 无论输入数据如何分布，时间复杂度都相同 |
| 最差情况 | O(n log n) | 在所有情况下表现一致 |
| 空间复杂度 | O(n) | 需要与原始数组相同大小的额外空间 |
与其他排序算法比较
归并排序 vs 快速排序
归并排序：稳定排序，时间复杂度稳定O(n log n)，需要额外空间
快速排序：不稳定排序，平均O(n log n)，最差O(n²)，原地排序
归并排序 vs 堆排序
归并排序：稳定，需要O(n)空间，适合外部排序
堆排序：不稳定，原地排序，O(1)空间，但缓存不友好
发表评论