排序算法——归并排序
一、介绍
「归并排序mergesort」是一种基于分治策略的排序算法，包含“划分”和“合并”阶段。
1. 划分阶段：通过递归不断地将数组从中点处分开，将长数组的排序问题转换为短数组的排序问题。
2. 合并阶段：当子数组长度为1时终止划分，开始合并，持续地将左右两个较短的有序数组合并为一个较长的有序数组，直至结束。
二、算法流程
“划分阶段”从顶至底递归地将数组从中点切分为两个子数组。
1. 计算数组中点mid ，递归划分左子数组（区间[left, mid] ）和右子数组（区间[mid + 1, right] ）。
2. 递归执行步骤1.，直至子数组区间长度为1时，终止递归划分。“合并阶段”从底至顶地将左子数组和右子数组合并为一个有序数组。需要注意的是，从长度为1的子数组开始合并，合并阶段中的每个子数组都是有序的。
观察发现，归并排序与二叉树后序遍历的递归顺序是一致的。
‧后序遍历：先递归左子树，再递归右子树，最后处理根节点。
‧归并排序：先递归左子数组，再递归右子数组，最后处理合并。
三、完整代码
def merge(nums: list[int], left: int, mid: int, right: int):"""合并左子数组和右子数组"""# 左子数组区间为 [left, mid], 右子数组区间为 [mid+1, right]# 创建一个临时数组 tmp ，用于存放合并后的结果tmp = [0] * (right - left + 1)# 初始化左子数组和右子数组的起始索引i, j, k = left, mid + 1, 0# 当左右子数组都还有元素时，进行比较并将较小的元素复制到临时数组中while i <= mid and j <= right:if nums[i] <= nums[j]:tmp[k] = nums[i]i += 1else:tmp[k] = nums[j]j += 1k += 1# 将左子数组和右子数组的剩余元素复制到临时数组中while i <= mid:tmp[k] = nums[i]i += 1k += 1while j <= right:tmp[k] = nums[j]j += 1k += 1# 将临时数组 tmp 中的元素复制回原数组 nums 的对应区间for k in range(0, len(tmp)):nums[left + k] = tmp[k]def merge_sort(nums: list[int], left: int, right: int):"""归并排序"""# 终止条件if left >= right:return # 当子数组长度为 1 时终止递归# 划分阶段mid = (left + right) // 2 # 计算中点merge_sort(nums, left, mid) # 递归左子数组merge_sort(nums, mid + 1, right) # 递归右子数组# 合并阶段merge(nums, left, mid, right)"""Driver Code"""
if __name__ == "__main__":nums = [7, 3, 2, 6, 0, 1, 5, 4]merge_sort(nums, 0, len(nums) - 1)print("归并排序完成后 nums =", nums)
1）merge_sort 函数的执行顺序是：先完全递归处理左子数组，再完全递归处理右子数组，最后合并左右子数组。
以数组 [3, 1, 4, 2] 的调用栈为例：
1. merge_sort(0,3) → 调用 merge_sort(0,1)（左子数组）。
2. merge_sort(0,1) → 调用 merge_sort(0,0)（左子数组）。
3. merge_sort(0,0) 返回 → 调用 merge_sort(1,1)（右子数组）。
4. merge_sort(1,1) 返回 → 合并 [0,0] 和 [1,1]。
5. merge_sort(0,1) 返回 → 调用 merge_sort(2,3)（右子数组）。
6. 递归处理右子数组的过程类似，最终合并整个数组。
2）实现合并函数 merge() 存在以下难点。
‧ 需要特别注意各个变量的含义。 nums 的待合并区间为[left, right] ，但由于 tmp 仅复制了 nums 该区间的元素，因此tmp对应区间为[0, right- left] 。
‧ 在比较 tmp[i] 和 tmp[j] 的大小时，还需考虑子数组遍历完成后的索引越界问题，即 i > leftEnd 和 j > rightEnd 的情况。索引越界的优先级是最高的，如果左子数组已经被合并完了，那么不需要继续比较，直接合并右子数组元素即可。
四、算法特性
‧ 时间复杂度𝑂(𝑛log𝑛)、非自适应排序：划分产生高度为log𝑛的递归树，每层合并的总操作数量为n，因此总体时间复杂度为𝑂(𝑛log𝑛)。
‧ 空间复杂度𝑂(𝑛)、非原地排序：递归深度为log𝑛，使用𝑂(log𝑛)大小的栈帧空间。合并操作需要借助辅助数组实现，使用𝑂(𝑛)大小的额外空间。
‧ 稳定排序：在合并过程中，相等元素的次序保持不变。