教程目录

想要实际看看算法是如何工作的吗?

通过交互式可视化深入理解算法运行过程

查看算法可视化

介绍

归并排序(Merge Sort)是一种高效且稳定的“分治”排序算法。其核心策略可以概括为“先递归拆分,再有序合并”。它会持续地将一个大数组对半切分,直到每个部分都只剩一个元素(此时天然有序)。接着,再反向地将这些相邻的有序部分两两配对,按大小顺序合并成一个更长的有序数组,不断重复此过程,直到最终还原成一个完整的有序序列。

归并排序的性能极其稳定,无论原始序列是好是坏,时间复杂度都保持在卓越的 O(nlogn)。与快速排序的“就地交换”不同,它通过“有序合并”实现排序,这一特性也保证了其排序的稳定性(相同元素的原始相对顺序在排序后不会改变),但通常需要额外的存储空间来辅助合并操作。

算法步骤

  1. 将待排序数组递归地分割成两半,直到每个子数组只包含一个元素(此时认为子数组已排序)
  2. 递归地合并相邻的子数组,合并时比较两个子数组的元素,按顺序放入临时数组(核心)
  3. 将临时数组中的元素复制回原数组对应的位置
  4. 重复步骤2和3,直到所有子数组合并成一个完整的有序数组

核心特性

  • 分治策略:将问题分解为更小的子问题,再将子问题的解合并
  • 稳定排序:相等元素的相对位置在排序后不会改变
  • 时间复杂度:最好、最坏、平均情况均为 O(nlogn)
  • 空间复杂度:需要 O(n) 的额外空间
  • 非原地排序:需要额外空间来存储临时数组

...

目录