深入理解归并排序：分治艺术的经典实践

2025/4/17 14:42:03 来源：https://blog.csdn.net/qq_39842184/article/details/146966205 浏览: 次关键词：深入理解归并排序：分治艺术的经典实践

归并排序（Merge Sort）是分治算法思想的经典体现，凭借稳定的 O(n log n) 时间复杂度，成为处理大规模数据的可靠选择。本文将从算法原理到链表实现，全面解析这一优雅的排序算法。

一、算法流程解析

1. 分治策略（Divide and Conquer）

分解阶段：递归地将当前数组拆分为两个子数组，直至每个子数组只剩单个元素
解决阶段：对最小单元（单元素数组）天然有序的情况进行处理
合并阶段：将两个已排序的子数组合并为一个有序数组

2. 合并过程详解

function merge(left: number[], right: number[]): number[] {const result: number[] = [];let i = 0, j = 0;// 双指针遍历比较while (i < left.length && j < right.length) {if (left[i] <= right[j]) {result.push(left[i++]);} else {result.push(right[j++]);}}// 处理剩余元素return result.concat(left.slice(i)).concat(right.slice(j));
}

二、算法特性分析

1. 时间复杂度

最佳/最差/平均时间复杂度均为 O(n log n)
推导公式：T(n) = 2T(n/2) + O(n)

2. 空间复杂度

数组实现：O(n) 临时存储空间
链表实现：O(1) 原地修改指针（递归栈空间除外）

3. 稳定性

稳定排序算法（合并时优先选择左半部分元素）

4. 适用场景

大数据量排序
链表排序
需要稳定性的场景

三、链表排序优势

相比数组实现，归并排序在链表排序中展现独特优势：

空间优化：合并过程只需修改指针，无需额外存储空间
天然适配：链表节点离散存储，避免数组的随机访问需求
高效拆分：快慢指针法可在 O(n) 时间复杂度内找到链表中点

四、TypeScript 链表实现

class ListNode {constructor(public val: number = 0, public next: ListNode | null = null) {}
}// 合并两个有序链表
function mergeLists(l1: ListNode | null, l2: ListNode | null): ListNode | null {const dummy = new ListNode();let current = dummy;while (l1 && l2) {if (l1.val <= l2.val) {current.next = l1;l1 = l1.next;} else {current.next = l2;l2 = l2.next;}current = current.next;}current.next = l1 || l2;return dummy.next;
}// 归并排序主函数
function mergeSort(head: ListNode | null): ListNode | null {if (!head?.next) return head;// 快慢指针找中点let slow: ListNode = head;let fast: ListNode | null = head.next;while (fast?.next) {slow = slow.next!;fast = fast.next.next;}// 分割链表const mid = slow.next;slow.next = null;// 递归排序const left = mergeSort(head);const right = mergeSort(mid);return mergeLists(left, right);
}

五、使用示例

// 创建测试链表：4 -> 2 -> 1 -> 3
const head = new ListNode(4);
head.next = new ListNode(2);
head.next.next = new ListNode(1);
head.next.next.next = new ListNode(3);// 执行排序
const sorted = mergeSort(head);// 输出结果：1 -> 2 -> 3 -> 4
let current = sorted;
while (current) {console.log(current.val + ' -> ');current = current.next;
}