【一周一算法】第三周：归并排序 · 思考题与练习详解

本文最后更新于：2025年11月2日 晚上

🧠 归并排序 · 思考题与练习详解

“理解递归的最好方式，就是亲手画出递归树；理解合并的最好方式，就是亲手实现链表版本。”

🧩 思考题一：链表上的归并排序

❓ 问题

为什么归并排序在链表排序中表现非常优秀？

💡 详解

核心答案：因为链表的合并操作可以在 O(1)O(1) 的额外空间内完成，避免了数组版本中 O(n)O(n) 的空间开销。

让我们通过代码对比来理解：

🔹 数组版本的合并（需要额外空间）

1
2
3
4
5
// 数组合并：需要 O(n) 额外空间
void merge(vector<int>& arr, int left, int mid, int right) {
    vector<int> temp(right - left + 1);  // 🚨 额外空间开销
    // ... 合并逻辑
}

🔹 链表版本的合并（原地操作）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// 链表节点定义
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

// 链表合并：O(1) 额外空间
ListNode* mergeLists(ListNode* l1, ListNode* l2) {
    ListNode dummy(0);        // 🎯 仅使用一个哨兵节点
    ListNode* tail = &dummy;
    
    while (l1 && l2) {
        if (l1->val <= l2->val) {
            tail->next = l1;
            l1 = l1->next;
        } else {
            tail->next = l2;
            l2 = l2->next;
        }
        tail = tail->next;
    }
    
    tail->next = l1 ? l1 : l2;
    return dummy.next;
}

📊 性能对比

特性数组版本链表版本
空间复杂度O(n)O(n)O(log⁡n)O(\log n)（递归栈）
合并操作需要拷贝数据直接修改指针
缓存友好性✅ 好❌ 差（内存不连续）
适用场景随机访问需求动态数据结构

🎯 LeetCode 实战

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
// LeetCode #148 - 链表排序
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if (!head || !head->next) return head;
        
        // 快慢指针找中点
        ListNode* slow = head;
        ListNode* fast = head->next;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        
        // 分割链表
        ListNode* mid = slow->next;
        slow->next = nullptr;
        
        // 递归排序
        ListNode* left = sortList(head);
        ListNode* right = sortList(mid);
        
        // 合并
        return mergeLists(left, right);
    }
    
private:
    ListNode* mergeLists(ListNode* l1, ListNode* l2) {
        ListNode dummy(0);
        ListNode* tail = &dummy;
        
        while (l1 && l2) {
            if (l1->val <= l2->val) {
                tail->next = l1;
                l1 = l1->next;
            } else {
                tail->next = l2;
                l2 = l2->next;
            }
            tail = tail->next;
        }
        
        tail->next = l1 ? l1 : l2;
        return dummy.next;
    }
};

🔍 思考题二：递归深度计算

❓ 问题

若数组长度是 1024，递归深度是多少？

💡 详解

直接计算：

log⁡21024=10\log_2 1024 = 10

递归树可视化：

1
2
3
4
5
层级 0: [0..1023]        (大小: 1024)
层级 1: [0..511] [512..1023]  (大小: 512)
层级 2: [0..255] [256..511] ... (大小: 256)
...
层级 10: [0] [1] [2] ... [1023] (大小: 1)

代码验证：

1
2
3
4
5
6
7
8
int calculateDepth(int n, int currentDepth = 0) {
    if (n <= 1) return currentDepth;
    return calculateDepth(n / 2, currentDepth + 1);
}

// 测试
cout << "1024的递归深度: " << calculateDepth(1024) << endl;
// 输出: 1024的递归深度: 10

🎯 通用公式

对于长度为 nn 的数组，归并排序递归深度为：

深度=⌈log⁡2n⌉\text{深度} = \lceil \log_2 n \rceil

数组长度递归深度递归调用次数
16431
1024102047
1,048,57620~2百万

⚡ 思考题三：迭代版归并排序

❓ 问题

请尝试实现迭代版（非递归版）归并排序

💡 详解

迭代版本避免了递归调用，使用循环自底向上合并：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <iostream>
#include <vector>
#include <algorithm>

void iterativeMergeSort(std::vector<int>& arr) {
    int n = arr.size();
    std::vector<int> temp(n);
    
    // 🎯 从大小为1的子数组开始，每次翻倍
    for (int size = 1; size < n; size *= 2) {
        // 遍历所有成对的子数组
        for (int leftStart = 0; leftStart < n; leftStart += 2 * size) {
            int mid = std::min(leftStart + size - 1, n - 1);
            int rightEnd = std::min(leftStart + 2 * size - 1, n - 1);
            
            // 合并 arr[leftStart..mid] 和 arr[mid+1..rightEnd]
            iterativeMerge(arr, temp, leftStart, mid, rightEnd);
        }
    }
}

void iterativeMerge(std::vector<int>& arr, std::vector<int>& temp, 
                   int left, int mid, int right) {
    int i = left, j = mid + 1, k = left;
    
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }
    
    while (i <= mid) temp[k++] = arr[i++];
    while (j <= right) temp[k++] = arr[j++];
    
    // 拷贝回原数组
    for (int idx = left; idx <= right; ++idx) {
        arr[idx] = temp[idx];
    }
}

// 测试
int main() {
    std::vector<int> arr = {38, 27, 43, 3, 9, 82, 10};
    iterativeMergeSort(arr);
    
    std::cout << "迭代版排序结果: ";
    for (int num : arr) std::cout << num << " ";
    std::cout << std::endl;
}

🔄 执行过程示例

1
2
3
4
5
6
7
8
9
10
初始: [38, 27, 43, 3, 9, 82, 10]

size=1: 合并相邻元素
[27, 38] [3, 43] [9, 82] [10]

size=2: 合并大小为2的块
[3, 27, 38, 43] [9, 10, 82]

size=4: 合并大小为4的块
[3, 9, 10, 27, 38, 43, 82]

📊 递归 vs 迭代对比

特性递归版本迭代版本
代码可读性✅ 更直观❌ 稍复杂
空间开销O(n+log⁡n)O(n + \log n)O(n)O(n)
函数调用有递归开销无递归开销
缓存友好❌ 差✅ 更好

🎯 思考题四：单缓冲区合并优化

❓ 问题

你能在 merge() 函数中只用一个缓冲区完成左右合并吗？

💡 详解

挑战：传统的合并需要两个临时数组 L 和 R，能否只用一个？

解决方案：使用单个缓冲区，但需要巧妙的拷贝策略：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void optimizedMerge(std::vector<int>& arr, int left, int mid, int right) {
    // 🎯 只使用一个临时缓冲区
    std::vector<int> buffer(arr.begin() + left, arr.begin() + right + 1);
    
    int n1 = mid - left + 1;    // 左半部分长度
    int i = 0, j = n1, k = left;  // i: 左半指针, j: 右半指针, k: 原数组指针
    
    while (i < n1 && j < buffer.size()) {
        if (buffer[i] <= buffer[j]) {
            arr[k++] = buffer[i++];
        } else {
            arr[k++] = buffer[j++];
        }
    }
    
    // 处理剩余元素
    while (i < n1) arr[k++] = buffer[i++];
    while (j < buffer.size()) arr[k++] = buffer[j++];
}

🔄 合并过程演示

1
2
3
4
5
6
7
8
9
10
11
12
原数组: [3, 27, 38, 43, 9, 10, 82]
left=0, mid=3, right=6

缓冲区: [3, 27, 38, 43, 9, 10, 82]
        ↑i        ↑j

比较 buffer[i]=3 vs buffer[j]=9 → 取3
比较 buffer[i]=27 vs buffer[j]=9 → 取9
比较 buffer[i]=27 vs buffer[j]=10 → 取10
比较 buffer[i]=27 vs buffer[j]=82 → 取27
...
最终: [3, 9, 10, 27, 38, 43, 82]

📈 空间优化效果

版本临时空间说明
传统版本2×n2=n2 \times \frac{n}{2} = n两个临时数组
优化版本nn一个缓冲区
链表版本O(1)O(1)仅哨兵节点

虽然空间复杂度仍是 O(n)O(n)，但：

  • 减少内存分配次数
  • 代码更简洁
  • 实际性能可能更好

🚀 扩展练习

🧩 练习1：归并排序的性能测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <chrono>
#include <random>

void performanceTest() {
    for (int size : {1000, 10000, 100000, 1000000}) {
        std::vector<int> arr(size);
        std::random_device rd;
        std::mt19937 gen(rd());
        std::uniform_int_distribution<> dis(1, size);
        
        for (int i = 0; i < size; ++i) {
            arr[i] = dis(gen);
        }
        
        auto start = std::chrono::high_resolution_clock::now();
        mergeSort(arr, 0, arr.size() - 1);
        auto end = std::chrono::high_resolution_clock::now();
        
        auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);
        std::cout << "大小 " << size << ": " << duration.count() << " ms" << std::endl;
    }
}

🧩 练习2：归并排序的稳定版本

确保在相等时保持原始顺序：

1
2
3
4
5
6
7
8
void stableMerge(std::vector<int>& arr, int left, int mid, int right) {
    // 关键：使用 <= 而不是 < 来保持稳定性
    if (L[i] <= R[j]) {  // 🎯 相等时优先取左边的
        arr[k++] = L[i++];
    } else {
        arr[k++] = R[j++];
    }
}

🧩 练习3：多路归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
// 三路归并排序
void threeWayMergeSort(std::vector<int>& arr, int left, int right) {
    if (right - left < 2) return;
    
    int third1 = left + (right - left) / 3;
    int third2 = left + 2 * (right - left) / 3;
    
    threeWayMergeSort(arr, left, third1);
    threeWayMergeSort(arr, third1 + 1, third2);
    threeWayMergeSort(arr, third2 + 1, right);
    
    threeWayMerge(arr, left, third1, third2, right);
}

💎 总结

通过这四个思考题，我们深入理解了：

  1. 数据结构适应性：链表上的归并排序空间效率更高
  2. 递归本质：深度与数据规模的对数关系
  3. 算法变形：迭代版本避免递归开销
  4. 空间优化：单缓冲区合并的技巧

🎯 “优秀的算法工程师不仅会使用标准实现，更懂得根据具体场景选择最优变种。”

这些深入理解为我们学习更复杂的分治算法（如快速排序、外部排序）奠定了坚实基础。

一周一算法
#算法 #C++ #归并排序 #思考与练习
【一周一算法】第三周：归并排序 · 思考题与练习详解
https://jinbilianshao.github.io/2025/11/02/【一周一算法】第三周：-归并排序-·-思考题与练习详解/
作者
连思鑫
发布于
2025年11月2日
许可协议