11.6 归并排序¶
归并排序(merge sort)是一种基于分治策略的排序算法,包含图 11-10 所示的“划分”和“合并”阶段。
- 划分阶段:通过递归不断地将数组从中点处分开,将长数组的排序问题转换为短数组的排序问题。
- 合并阶段:当子数组长度为 1 时终止划分,开始合并,持续地将左右两个较短的有序数组合并为一个较长的有序数组,直至结束。
图 11-10 归并排序的划分与合并阶段
图解 11-10:归并排序的划分与合并
先按位置中点将数组递归拆分为单元素子数组,再逐层将相邻有序子数组合并为完整有序数组。
输入数组为 [7, 3, 2, 6, 0, 1, 5, 4]。划分阶段只按位置中点将数组不断对半切分,不按数值大小分组;当子数组长度为 1 时停止划分,因为单元素子数组天然有序。
| 阶段 | 子数组 |
|---|---|
| 输入 | [7, 3, 2, 6, 0, 1, 5, 4] |
| 划分为长度4 | [7, 3, 2, 6];[0, 1, 5, 4] |
| 划分为长度2 | [7, 3];[2, 6];[0, 1];[5, 4] |
| 单元素,停止划分 | [7];[3];[2];[6];[0];[1];[5];[4] |
| 合并为长度2 | [3, 7];[2, 6];[0, 1];[4, 5] |
| 合并为长度4 | [2, 3, 6, 7];[0, 1, 4, 5] |
| 合并为长度8 | [0, 1, 2, 3, 4, 5, 6, 7] |
上半部分经过三层对半划分,拆解为 8 个单元素子数组(触发递归终止条件);下半部分自底向上逐层两两归并。每次合并的两个输入子数组都已各自升序排列:算法比较两侧尚未取出的首元素,先将较小者放入结果区间,待一侧取尽后直接追加另一侧的剩余元素,从而保证每次合并的结果依然有序。图中下半部分的交叉箭头用于追踪各元素进入下一层合并结果的目标位置,不表示两两原地交换。
图按递归树层级并列展示数据依赖关系;本节代码先完整处理左分支,再处理右分支,最后合并左右结果。
11.6.1 算法流程¶
如图 11-11 所示,“划分阶段”从顶至底递归地将数组从中点切分为两个子数组。
- 计算数组中点
mid,递归划分左子数组(区间[left, mid])和右子数组(区间[mid + 1, right])。 - 递归执行步骤
1.,直至子数组区间长度为 1 时终止。
“合并阶段”从底至顶地将左子数组和右子数组合并为一个有序数组。需要注意的是,从长度为 1 的子数组开始合并,合并阶段中的每个子数组都是有序的。
图 11-11 归并排序步骤
图解 11-11:四元素归并排序的递归执行顺序
先将左半 [7,3] 排成 [3,7],再处理右半 [2,6],最后合并为 [2,3,6,7]。
本图输入是四元素数组 [7,3,2,6],索引为 0 至 3。先递归处理左半,再处理右半,最后合并两边的有序结果。
图中保留已经展开的子问题和返回结果,用来表示递归调用历史;它们并非同一数组在当前时刻的多个版本。长度为 1 的子数组直接返回。
下方“归并调用与返回记录”按首次出现的步号汇总十条记录,第 N 步已经显示的完整历史是该表中首次出现步号为 1 至 N 的记录。表中的输入快照不会被返回结果覆盖。合并时逐次比较两边首个未取元素,取较小值;一边取完后接上另一边余项。十步是图示状态,不是十次元素比较。
| 索引 | 值 |
|---|---|
| 0 | 7 |
| 1 | 3 |
| 2 | 2 |
| 3 | 6 |
| 首次出现步号 | 子问题或结果 | 数组 | 含义 |
|---|---|---|---|
| 1 | 完整输入 | [7, 3, 2, 6] | 划分时的输入快照 |
| 2 | 左半输入 | [7, 3] | 划分时的输入快照 |
| 3 | 单元素 7 | [7] | 单元素,直接返回 |
| 4 | 单元素 3 | [3] | 单元素,直接返回 |
| 5 | 左半返回结果 | [3, 7] | 有序合并结果 |
| 6 | 右半输入 | [2, 6] | 划分时的输入快照 |
| 7 | 单元素 2 | [2] | 单元素,直接返回 |
| 8 | 单元素 6 | [6] | 单元素,直接返回 |
| 9 | 右半返回结果 | [2, 6] | 有序合并结果 |
| 10 | 顶层返回结果 | [2, 3, 6, 7] | 有序合并结果 |
开始排序四个元素
对 [7, 3, 2, 6] 启动顶层归并排序,左右子问题尚未展开。完整已显示记录见“归并调用与返回记录”中首次出现步号为 1 的记录。
递归处理左半
按先左后右的次序进入左半 [7, 3];右半 [2, 6] 尚未展开。完整已显示记录见“归并调用与返回记录”中首次出现步号为 1 至 2 的记录。
左半分出单元素 7
划分左半 [7, 3],先进入单元素 [7],因长度为 1 而直接返回;[3] 和右半尚未展开。完整已显示记录见“归并调用与返回记录”中首次出现步号为 1 至 3 的记录。
左半分出单元素 3
单元素 [7] 返回后,进入单元素 [3] 并直接返回。左半两个单元素均已就绪,准备合并;右半尚未展开。完整已显示记录见“归并调用与返回记录”中首次出现步号为 1 至 4 的记录。
左半合并为 [3,7]
比较左半返回的 [7] 与 [3],合并为 [3, 7] 并返回。右半尚未展开;图中仍保留的 [7, 3] 是调用时的输入快照。完整已显示记录见“归并调用与返回记录”中首次出现步号为 1 至 5 的记录。
递归处理右半
左半已返回有序结果 [3, 7],现在进入右半 [2, 6];其两个单元素尚未展开。完整已显示记录见“归并调用与返回记录”中首次出现步号为 1 至 6 的记录。
右半分出单元素 2
左半已返回有序结果 [3, 7]。划分右半 [2, 6],先进入单元素 [2] 并直接返回;[6] 尚未展开。完整已显示记录见“归并调用与返回记录”中首次出现步号为 1 至 7 的记录。
右半分出单元素 6
右半的 [2] 返回后,进入单元素 [6] 并直接返回。右半两个单元素均已就绪,准备合并;左半结果仍为 [3, 7]。完整已显示记录见“归并调用与返回记录”中首次出现步号为 1 至 8 的记录。
右半合并为 [2,6]
将右半返回的 [2] 与 [6] 合并为 [2, 6]。左右结果 [3, 7]、[2, 6] 均已就绪,准备顶层合并。完整已显示记录见“归并调用与返回记录”中首次出现步号为 1 至 9 的记录。
合并左右两半
在顶层比较 [3, 7] 与 [2, 6] 的首个未取元素:先取 2,再取 3,再取 6,右半取完后接上左半的 7。最终得到 [2, 3, 6, 7],排序完成;图中仍保留全部输入快照与返回结果。完整已显示记录见“归并调用与返回记录”中首次出现步号为 1 至 10 的记录。
观察发现,归并排序与二叉树后序遍历的递归顺序是一致的。
- 后序遍历:先递归左子树,再递归右子树,最后处理根节点。
- 归并排序:先递归左子数组,再递归右子数组,最后处理合并。
归并排序的实现如以下代码所示。请注意,nums 的待合并区间为 [left, right] ,而 tmp 的对应区间为 [0, right - left] 。
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 += 1
else:
tmp[k] = nums[j]
j += 1
k += 1
# 将左子数组和右子数组的剩余元素复制到临时数组中
while i <= mid:
tmp[k] = nums[i]
i += 1
k += 1
while j <= right:
tmp[k] = nums[j]
j += 1
k += 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)
/* 合并左子数组和右子数组 */
void merge(vector<int> &nums, int left, int mid, int right) {
// 左子数组区间为 [left, mid], 右子数组区间为 [mid+1, right]
// 创建一个临时数组 tmp ,用于存放合并后的结果
vector<int> tmp(right - left + 1);
// 初始化左子数组和右子数组的起始索引
int i = left, j = mid + 1, k = 0;
// 当左右子数组都还有元素时,进行比较并将较小的元素复制到临时数组中
while (i <= mid && j <= right) {
if (nums[i] <= nums[j])
tmp[k++] = nums[i++];
else
tmp[k++] = nums[j++];
}
// 将左子数组和右子数组的剩余元素复制到临时数组中
while (i <= mid) {
tmp[k++] = nums[i++];
}
while (j <= right) {
tmp[k++] = nums[j++];
}
// 将临时数组 tmp 中的元素复制回原数组 nums 的对应区间
for (k = 0; k < tmp.size(); k++) {
nums[left + k] = tmp[k];
}
}
/* 归并排序 */
void mergeSort(vector<int> &nums, int left, int right) {
// 终止条件
if (left >= right)
return; // 当子数组长度为 1 时终止递归
// 划分阶段
int mid = left + (right - left) / 2; // 计算中点
mergeSort(nums, left, mid); // 递归左子数组
mergeSort(nums, mid + 1, right); // 递归右子数组
// 合并阶段
merge(nums, left, mid, right);
}
/* 合并左子数组和右子数组 */
void merge(int[] nums, int left, int mid, int right) {
// 左子数组区间为 [left, mid], 右子数组区间为 [mid+1, right]
// 创建一个临时数组 tmp ,用于存放合并后的结果
int[] tmp = new int[right - left + 1];
// 初始化左子数组和右子数组的起始索引
int i = left, j = mid + 1, k = 0;
// 当左右子数组都还有元素时,进行比较并将较小的元素复制到临时数组中
while (i <= mid && j <= right) {
if (nums[i] <= nums[j])
tmp[k++] = nums[i++];
else
tmp[k++] = nums[j++];
}
// 将左子数组和右子数组的剩余元素复制到临时数组中
while (i <= mid) {
tmp[k++] = nums[i++];
}
while (j <= right) {
tmp[k++] = nums[j++];
}
// 将临时数组 tmp 中的元素复制回原数组 nums 的对应区间
for (k = 0; k < tmp.length; k++) {
nums[left + k] = tmp[k];
}
}
/* 归并排序 */
void mergeSort(int[] nums, int left, int right) {
// 终止条件
if (left >= right)
return; // 当子数组长度为 1 时终止递归
// 划分阶段
int mid = left + (right - left) / 2; // 计算中点
mergeSort(nums, left, mid); // 递归左子数组
mergeSort(nums, mid + 1, right); // 递归右子数组
// 合并阶段
merge(nums, left, mid, right);
}
/* 合并左子数组和右子数组 */
void Merge(int[] nums, int left, int mid, int right) {
// 左子数组区间为 [left, mid], 右子数组区间为 [mid+1, right]
// 创建一个临时数组 tmp ,用于存放合并后的结果
int[] tmp = new int[right - left + 1];
// 初始化左子数组和右子数组的起始索引
int i = left, j = mid + 1, k = 0;
// 当左右子数组都还有元素时,进行比较并将较小的元素复制到临时数组中
while (i <= mid && j <= right) {
if (nums[i] <= nums[j])
tmp[k++] = nums[i++];
else
tmp[k++] = nums[j++];
}
// 将左子数组和右子数组的剩余元素复制到临时数组中
while (i <= mid) {
tmp[k++] = nums[i++];
}
while (j <= right) {
tmp[k++] = nums[j++];
}
// 将临时数组 tmp 中的元素复制回原数组 nums 的对应区间
for (k = 0; k < tmp.Length; ++k) {
nums[left + k] = tmp[k];
}
}
/* 归并排序 */
void MergeSort(int[] nums, int left, int right) {
// 终止条件
if (left >= right) return; // 当子数组长度为 1 时终止递归
// 划分阶段
int mid = left + (right - left) / 2; // 计算中点
MergeSort(nums, left, mid); // 递归左子数组
MergeSort(nums, mid + 1, right); // 递归右子数组
// 合并阶段
Merge(nums, left, mid, right);
}
/* 合并左子数组和右子数组 */
func merge(nums []int, left, mid, right int) {
// 左子数组区间为 [left, mid], 右子数组区间为 [mid+1, right]
// 创建一个临时数组 tmp ,用于存放合并后的结果
tmp := make([]int, right-left+1)
// 初始化左子数组和右子数组的起始索引
i, j, k := left, mid+1, 0
// 当左右子数组都还有元素时,进行比较并将较小的元素复制到临时数组中
for i <= mid && j <= right {
if nums[i] <= nums[j] {
tmp[k] = nums[i]
i++
} else {
tmp[k] = nums[j]
j++
}
k++
}
// 将左子数组和右子数组的剩余元素复制到临时数组中
for i <= mid {
tmp[k] = nums[i]
i++
k++
}
for j <= right {
tmp[k] = nums[j]
j++
k++
}
// 将临时数组 tmp 中的元素复制回原数组 nums 的对应区间
for k := 0; k < len(tmp); k++ {
nums[left+k] = tmp[k]
}
}
/* 归并排序 */
func mergeSort(nums []int, left, right int) {
// 终止条件
if left >= right {
return
}
// 划分阶段
mid := left + (right - left) / 2
mergeSort(nums, left, mid)
mergeSort(nums, mid+1, right)
// 合并阶段
merge(nums, left, mid, right)
}
/* 合并左子数组和右子数组 */
func merge(nums: inout [Int], left: Int, mid: Int, right: Int) {
// 左子数组区间为 [left, mid], 右子数组区间为 [mid+1, right]
// 创建一个临时数组 tmp ,用于存放合并后的结果
var tmp = Array(repeating: 0, count: right - left + 1)
// 初始化左子数组和右子数组的起始索引
var i = left, j = mid + 1, k = 0
// 当左右子数组都还有元素时,进行比较并将较小的元素复制到临时数组中
while i <= mid, j <= right {
if nums[i] <= nums[j] {
tmp[k] = nums[i]
i += 1
} else {
tmp[k] = nums[j]
j += 1
}
k += 1
}
// 将左子数组和右子数组的剩余元素复制到临时数组中
while i <= mid {
tmp[k] = nums[i]
i += 1
k += 1
}
while j <= right {
tmp[k] = nums[j]
j += 1
k += 1
}
// 将临时数组 tmp 中的元素复制回原数组 nums 的对应区间
for k in tmp.indices {
nums[left + k] = tmp[k]
}
}
/* 归并排序 */
func mergeSort(nums: inout [Int], left: Int, right: Int) {
// 终止条件
if left >= right { // 当子数组长度为 1 时终止递归
return
}
// 划分阶段
let mid = left + (right - left) / 2 // 计算中点
mergeSort(nums: &nums, left: left, right: mid) // 递归左子数组
mergeSort(nums: &nums, left: mid + 1, right: right) // 递归右子数组
// 合并阶段
merge(nums: &nums, left: left, mid: mid, right: right)
}
/* 合并左子数组和右子数组 */
function merge(nums, left, mid, right) {
// 左子数组区间为 [left, mid], 右子数组区间为 [mid+1, right]
// 创建一个临时数组 tmp ,用于存放合并后的结果
const tmp = new Array(right - left + 1);
// 初始化左子数组和右子数组的起始索引
let i = left,
j = mid + 1,
k = 0;
// 当左右子数组都还有元素时,进行比较并将较小的元素复制到临时数组中
while (i <= mid && j <= right) {
if (nums[i] <= nums[j]) {
tmp[k++] = nums[i++];
} else {
tmp[k++] = nums[j++];
}
}
// 将左子数组和右子数组的剩余元素复制到临时数组中
while (i <= mid) {
tmp[k++] = nums[i++];
}
while (j <= right) {
tmp[k++] = nums[j++];
}
// 将临时数组 tmp 中的元素复制回原数组 nums 的对应区间
for (k = 0; k < tmp.length; k++) {
nums[left + k] = tmp[k];
}
}
/* 归并排序 */
function mergeSort(nums, left, right) {
// 终止条件
if (left >= right) return; // 当子数组长度为 1 时终止递归
// 划分阶段
let mid = Math.floor(left + (right - left) / 2); // 计算中点
mergeSort(nums, left, mid); // 递归左子数组
mergeSort(nums, mid + 1, right); // 递归右子数组
// 合并阶段
merge(nums, left, mid, right);
}
/* 合并左子数组和右子数组 */
function merge(nums: number[], left: number, mid: number, right: number): void {
// 左子数组区间为 [left, mid], 右子数组区间为 [mid+1, right]
// 创建一个临时数组 tmp ,用于存放合并后的结果
const tmp = new Array(right - left + 1);
// 初始化左子数组和右子数组的起始索引
let i = left,
j = mid + 1,
k = 0;
// 当左右子数组都还有元素时,进行比较并将较小的元素复制到临时数组中
while (i <= mid && j <= right) {
if (nums[i] <= nums[j]) {
tmp[k++] = nums[i++];
} else {
tmp[k++] = nums[j++];
}
}
// 将左子数组和右子数组的剩余元素复制到临时数组中
while (i <= mid) {
tmp[k++] = nums[i++];
}
while (j <= right) {
tmp[k++] = nums[j++];
}
// 将临时数组 tmp 中的元素复制回原数组 nums 的对应区间
for (k = 0; k < tmp.length; k++) {
nums[left + k] = tmp[k];
}
}
/* 归并排序 */
function mergeSort(nums: number[], left: number, right: number): void {
// 终止条件
if (left >= right) return; // 当子数组长度为 1 时终止递归
// 划分阶段
let mid = Math.floor(left + (right - left) / 2); // 计算中点
mergeSort(nums, left, mid); // 递归左子数组
mergeSort(nums, mid + 1, right); // 递归右子数组
// 合并阶段
merge(nums, left, mid, right);
}
/* 合并左子数组和右子数组 */
void merge(List<int> nums, int left, int mid, int right) {
// 左子数组区间为 [left, mid], 右子数组区间为 [mid+1, right]
// 创建一个临时数组 tmp ,用于存放合并后的结果
List<int> tmp = List.filled(right - left + 1, 0);
// 初始化左子数组和右子数组的起始索引
int i = left, j = mid + 1, k = 0;
// 当左右子数组都还有元素时,进行比较并将较小的元素复制到临时数组中
while (i <= mid && j <= right) {
if (nums[i] <= nums[j])
tmp[k++] = nums[i++];
else
tmp[k++] = nums[j++];
}
// 将左子数组和右子数组的剩余元素复制到临时数组中
while (i <= mid) {
tmp[k++] = nums[i++];
}
while (j <= right) {
tmp[k++] = nums[j++];
}
// 将临时数组 tmp 中的元素复制回原数组 nums 的对应区间
for (k = 0; k < tmp.length; k++) {
nums[left + k] = tmp[k];
}
}
/* 归并排序 */
void mergeSort(List<int> nums, int left, int right) {
// 终止条件
if (left >= right) return; // 当子数组长度为 1 时终止递归
// 划分阶段
int mid = left + (right - left) ~/ 2; // 计算中点
mergeSort(nums, left, mid); // 递归左子数组
mergeSort(nums, mid + 1, right); // 递归右子数组
// 合并阶段
merge(nums, left, mid, right);
}
/* 合并左子数组和右子数组 */
fn merge(nums: &mut [i32], left: usize, mid: usize, right: usize) {
// 左子数组区间为 [left, mid], 右子数组区间为 [mid+1, right]
// 创建一个临时数组 tmp ,用于存放合并后的结果
let tmp_size = right - left + 1;
let mut tmp = vec![0; tmp_size];
// 初始化左子数组和右子数组的起始索引
let (mut i, mut j, mut k) = (left, mid + 1, 0);
// 当左右子数组都还有元素时,进行比较并将较小的元素复制到临时数组中
while i <= mid && j <= right {
if nums[i] <= nums[j] {
tmp[k] = nums[i];
i += 1;
} else {
tmp[k] = nums[j];
j += 1;
}
k += 1;
}
// 将左子数组和右子数组的剩余元素复制到临时数组中
while i <= mid {
tmp[k] = nums[i];
k += 1;
i += 1;
}
while j <= right {
tmp[k] = nums[j];
k += 1;
j += 1;
}
// 将临时数组 tmp 中的元素复制回原数组 nums 的对应区间
for k in 0..tmp_size {
nums[left + k] = tmp[k];
}
}
/* 归并排序 */
fn merge_sort(nums: &mut [i32], left: usize, right: usize) {
// 终止条件
if left >= right {
return; // 当子数组长度为 1 时终止递归
}
// 划分阶段
let mid = left + (right - left) / 2; // 计算中点
merge_sort(nums, left, mid); // 递归左子数组
merge_sort(nums, mid + 1, right); // 递归右子数组
// 合并阶段
merge(nums, left, mid, right);
}
/* 合并左子数组和右子数组 */
void merge(int *nums, int left, int mid, int right) {
// 左子数组区间为 [left, mid], 右子数组区间为 [mid+1, right]
// 创建一个临时数组 tmp ,用于存放合并后的结果
int tmpSize = right - left + 1;
int *tmp = (int *)malloc(tmpSize * sizeof(int));
// 初始化左子数组和右子数组的起始索引
int i = left, j = mid + 1, k = 0;
// 当左右子数组都还有元素时,进行比较并将较小的元素复制到临时数组中
while (i <= mid && j <= right) {
if (nums[i] <= nums[j]) {
tmp[k++] = nums[i++];
} else {
tmp[k++] = nums[j++];
}
}
// 将左子数组和右子数组的剩余元素复制到临时数组中
while (i <= mid) {
tmp[k++] = nums[i++];
}
while (j <= right) {
tmp[k++] = nums[j++];
}
// 将临时数组 tmp 中的元素复制回原数组 nums 的对应区间
for (k = 0; k < tmpSize; ++k) {
nums[left + k] = tmp[k];
}
// 释放内存
free(tmp);
}
/* 归并排序 */
void mergeSort(int *nums, int left, int right) {
// 终止条件
if (left >= right)
return; // 当子数组长度为 1 时终止递归
// 划分阶段
int mid = left + (right - left) / 2; // 计算中点
mergeSort(nums, left, mid); // 递归左子数组
mergeSort(nums, mid + 1, right); // 递归右子数组
// 合并阶段
merge(nums, left, mid, right);
}
/* 合并左子数组和右子数组 */
fun merge(nums: IntArray, left: Int, mid: Int, right: Int) {
// 左子数组区间为 [left, mid], 右子数组区间为 [mid+1, right]
// 创建一个临时数组 tmp ,用于存放合并后的结果
val tmp = IntArray(right - left + 1)
// 初始化左子数组和右子数组的起始索引
var i = left
var j = mid + 1
var k = 0
// 当左右子数组都还有元素时,进行比较并将较小的元素复制到临时数组中
while (i <= mid && j <= right) {
if (nums[i] <= nums[j])
tmp[k++] = nums[i++]
else
tmp[k++] = nums[j++]
}
// 将左子数组和右子数组的剩余元素复制到临时数组中
while (i <= mid) {
tmp[k++] = nums[i++]
}
while (j <= right) {
tmp[k++] = nums[j++]
}
// 将临时数组 tmp 中的元素复制回原数组 nums 的对应区间
for (l in tmp.indices) {
nums[left + l] = tmp[l]
}
}
/* 归并排序 */
fun mergeSort(nums: IntArray, left: Int, right: Int) {
// 终止条件
if (left >= right) return // 当子数组长度为 1 时终止递归
// 划分阶段
val mid = left + (right - left) / 2 // 计算中点
mergeSort(nums, left, mid) // 递归左子数组
mergeSort(nums, mid + 1, right) // 递归右子数组
// 合并阶段
merge(nums, left, mid, right)
}
### 合并左子数组和右子数组 ###
def merge(nums, left, mid, right)
# 左子数组区间为 [left, mid], 右子数组区间为 [mid+1, right]
# 创建一个临时数组 tmp,用于存放合并后的结果
tmp = Array.new(right - left + 1, 0)
# 初始化左子数组和右子数组的起始索引
i, j, k = left, mid + 1, 0
# 当左右子数组都还有元素时,进行比较并将较小的元素复制到临时数组中
while i <= mid && j <= right
if nums[i] <= nums[j]
tmp[k] = nums[i]
i += 1
else
tmp[k] = nums[j]
j += 1
end
k += 1
end
# 将左子数组和右子数组的剩余元素复制到临时数组中
while i <= mid
tmp[k] = nums[i]
i += 1
k += 1
end
while j <= right
tmp[k] = nums[j]
j += 1
k += 1
end
# 将临时数组 tmp 中的元素复制回原数组 nums 的对应区间
(0...tmp.length).each do |k|
nums[left + k] = tmp[k]
end
end
### 归并排序 ###
def merge_sort(nums, left, right)
# 终止条件
# 当子数组长度为 1 时终止递归
return if left >= right
# 划分阶段
mid = left + (right - left) / 2 # 计算中点
merge_sort(nums, left, mid) # 递归左子数组
merge_sort(nums, mid + 1, right) # 递归右子数组
# 合并阶段
merge(nums, left, mid, right)
end
可视化运行
11.6.2 算法特性¶
- 时间复杂度为 \(O(n \log n)\)、非自适应排序:划分产生高度为 \(\log n\) 的递归树,每层合并的总操作数量为 \(n\) ,因此总体时间复杂度为 \(O(n \log n)\) 。
- 空间复杂度为 \(O(n)\)、非原地排序:递归深度为 \(\log n\) ,使用 \(O(\log n)\) 大小的栈帧空间。合并操作需要借助辅助数组实现,使用 \(O(n)\) 大小的额外空间。
- 稳定排序:在合并过程中,相等元素的次序保持不变。
11.6.3 链表排序¶
对于链表,归并排序相较于其他排序算法具有显著优势,可以将链表排序任务的空间复杂度优化至 \(O(1)\) 。
- 划分阶段:可以使用“迭代”替代“递归”来实现链表划分工作,从而省去递归使用的栈帧空间。
- 合并阶段:在链表中,节点增删操作仅需改变引用(指针)即可实现,因此合并阶段(将两个短有序链表合并为一个长有序链表)无须创建额外链表。
具体实现细节比较复杂,有兴趣的读者可以查阅相关资料进行学习。