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

时间：2025-04-07 21:27:20

归并排序（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. 适用场景

  • 大数据量排序

  • 链表排序

  • 需要稳定性的场景

三、链表排序优势

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

  1. 空间优化：合并过程只需修改指针，无需额外存储空间

  2. 天然适配：链表节点离散存储，避免数组的随机访问需求

  3. 高效拆分：快慢指针法可在 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;
}

六、总结

归并排序通过分治策略将复杂问题简单化，其稳定性和可预测的时间复杂度使其成为：

  • 大数据量场景的优选算法

  • 链表排序的标准解决方案

  • 外部排序（如大文件处理）的核心组件

如果对你有帮助，请帮忙点个赞 

相关文章