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

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

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

---

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

❓ 问题

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

💡 详解

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

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

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

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

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

// 链表节点定义
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(\log n)$（递归栈）
合并操作	需要拷贝数据	直接修改指针
缓存友好性	✅ 好	❌ 差（内存不连续）
适用场景	随机访问需求	动态数据结构

🎯 LeetCode 实战

// 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_2 1024 = 10$$

递归树可视化：

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

代码验证：

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

🎯 通用公式

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

$$\text{深度} = \lceil \log_2 n \rceil$$

数组长度	递归深度	递归调用次数
16	4	31
1024	10	2047
1,048,576	20	~2百万

---

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

❓ 问题

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

💡 详解

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

#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;
}

🔄 执行过程示例

初始: [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)$
函数调用	有递归开销	无递归开销
缓存友好	❌ 差	✅ 更好

---

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

❓ 问题

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

💡 详解

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

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

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++];
}

🔄 合并过程演示

原数组: [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 \times \frac{n}{2} = n$	两个临时数组
优化版本	$n$	一个缓冲区
链表版本	$O(1)$	仅哨兵节点

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

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

---

🚀 扩展练习

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

#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：归并排序的稳定版本

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

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：多路归并排序

// 三路归并排序
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. 空间优化：单缓冲区合并的技巧

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

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

---