排序算法归并排序
归并排序详解
归并排序（Merge Sort）是一种 分治算法，核心思想是将数组不断拆分为更小的子数组排序，再合并成有序数组。时间复杂度始终为 O(n log n)，稳定且效率高。
工作步骤：
- 分解：将数组从中点分为左右两部分
- 递归：对左右子数组分别递归排序
- 合并：将两个有序子数组合并为一个有序数组
案例：整理扑克牌
假设你有两堆已排序的扑克牌（左堆：[3, 5], 右堆：[1, 8]）需合并为一副有序牌：
- 比较两堆顶部的牌：左堆3 > 右堆1 → 取1放到新堆
- 再比较：左堆3 < 右堆8 → 取3
- 左堆剩5 < 8 → 取5
- 最后取右堆剩余的8 → 新堆[1, 3, 5, 8]
Python 代码实现
def merge_sort(arr):# 递归终止条件：单元素或空数组if len(arr) <= 1:return arrmid = 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 += 1else:result.append(right[j])j += 1# 添加剩余元素result.extend(left[i:])result.extend(right[j:])return result# 测试示例
if __name__ == "__main__":array = [38, 27, 43, 3, 9, 82, 10]print("原始数组：", array)sorted_array = merge_sort(array)print("排序结果：", sorted_array)输出示例：
原始数组： [38, 27, 43, 3, 9, 82, 10]
排序结果： [3, 9, 10, 27, 38, 43, 82]算法关键点
- 稳定性：
left[i] <= right[j]保证相等元素顺序不变 - 空间代价：需额外 O(n) 空间存储合并结果
- 高效场景：大数据量排序（远超冒泡/插入排序）
💡 现实应用：数据库排序、外排序（处理超大数据）
🔄 分治思想同样适用于快速排序，但归并的稳定性是其独特优势。
做题
我们需要对数组 a = {6, 5, 4, 3, 2, 1, 8, 8} 进行归并排序（升序），并找出完成最终归并排序的前一步的结果。
归并排序的基本步骤
- 分解：将数组递归地分成两半，直到每个子数组只有一个元素。
- 合并：将两个已排序的子数组合并成一个有序数组。
具体过程
初始数组：[6, 5, 4, 3, 2, 1, 8, 8]
第一次分解：
- 左半部分：
[6, 5, 4, 3] - 右半部分：
[2, 1, 8, 8]
- 左半部分：
对左半部分
[6, 5, 4, 3]分解：- 左：
[6, 5]→ 排序后：[5, 6] - 右：
[4, 3]→ 排序后：[3, 4] - 合并：
[5, 6]和[3, 4]→[3, 4, 5, 6]
- 左：
对右半部分
[2, 1, 8, 8]分解：- 左：
[2, 1]→ 排序后：[1, 2] - 右：
[8, 8]→ 排序后：[8, 8] - 合并：
[1, 2]和[8, 8]→[1, 2, 8, 8]
- 左：
最终合并的前一步：
- 左半部分已排序：
[3, 4, 5, 6] - 右半部分已排序：
[1, 2, 8, 8] - 下一步是将
[3, 4, 5, 6]和[1, 2, 8, 8]合并为[1, 2, 3, 4, 5, 6, 8, 8]。
- 左半部分已排序：
因此，完成最终归并排序的前一步的结果是：
- 左半部分：
[3, 4, 5, 6] - 右半部分：
[1, 2, 8, 8]
选项匹配
- Ⓐ
2, 1, 8, 8, 6, 5, 4, 3：错误，未体现归并排序的合并过程。 - Ⓑ
3, 4, 5, 6, 1, 2, 8, 8：正确，这是左半部分和右半部分分别排序后的结果。 - Ⓒ
1, 2, 3, 4, 5, 6, 8, 8：错误，这是最终排序结果，不是前一步。 - Ⓓ
6, 5, 4, 3, 2, 1, 8, 8：错误，这是初始数组。
正确答案：Ⓑ 3, 4, 5, 6, 1, 2, 8, 8