归并排序

排序算法

归并排序是一种高效、分治策略的排序算法,通过递归地将数组分为两半,分别排序后再合并,以实现整体排序。

时间复杂度:最佳 O(n log n) | 平均 O(n log n) | 最差 O(n log n)
空间复杂度:O(n)
稳定性:稳定

应用场景/前提条件

  • 适用于大规模数据
  • 适合链表排序
  • 需要稳定性时优先选择

算法讲解

介绍

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

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

算法步骤

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

核心特性

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

...