排序算法

排序算法是算法领域的基础核心内容，本质是将一组无序数据（如整数、字符串等）按照指定顺序（升序 / 降序）重新排列的方法。不同排序算法在时间复杂度、空间复杂度、稳定性、适用场景上差异极大，下面按「基础分类 + 核心特性 + 实现逻辑 + 适用场景」的框架，系统讲解主流排序算法，兼顾原理理解和实践应用。

1. 排序算法的核心评价维度

先明确衡量排序算法的关键指标，后续分析均围绕这些维度展开：

维度	说明
时间复杂度	最坏 / 平均 / 最好情况下的执行效率（如 、、）
空间复杂度	算法运行所需额外空间（原地排序：；非原地排序：如 、）
稳定性	排序后，值相等的元素相对位置是否保持不变（稳定：是；不稳定：否）
适用场景	适合的数据集规模、数据分布（如近乎有序、小规模、大规模）

2. 主流排序算法分类讲解

排序算法可按「核心思想」分为四大类：交换类、插入类、选择类、归并/分治类，还有特殊的线性时间排序（仅限特定条件）。

2.1 交换类排序：通过交换元素位置实现有序

核心逻辑：比较两个元素，若顺序错误则交换，直到整体有序。

2.1.1 冒泡排序（Bubble Sort）

• 原理：重复遍历数组，每次比较相邻元素，将较大（小）的元素逐步「冒泡」到数组末端（前端）。

• 核心步骤：

  1. 从数组头部开始，依次比较相邻元素 arr[i] 和 arr[i+1]
  2. 若 arr[i] > arr[i+1]，交换二者
  3. 一轮遍历后，最大元素已到数组末尾，缩小遍历范围（排除已排序的末尾）
  4. 重复直到无交换发生（提前终止优化）

• 特性：

  • 时间复杂度：最好 （近乎有序）、最坏 / 平均
  • 空间复杂度：（原地排序）
  • 稳定性：稳定（相等元素不交换）

• 适用场景：小规模数据、近乎有序的数据集（优化后效率较高）

2.1.2 快速排序（Quick Sort）

• 原理：分治思想 —— 选一个「基准值」，将数组分为「小于基准」和「大于基准」两部分，递归排序子数组。

• 核心步骤：

  1. 选基准值（如数组首元素、尾元素、随机元素，或三数取中法）
  2. 分区（Partition）：遍历数组，将小于基准的放左，大于的放右，基准归位
  3. 递归对左右子数组重复上述步骤

• 特性：

  • 时间复杂度：最好 / 平均 、最坏 （基准选到极值，如已排序数组选首元素）
  • 空间复杂度：（递归栈，原地排序）
  • 稳定性：不稳定（分区交换会打乱相等元素位置）

• 优化技巧：

  • 基准选择：三数取中法（选首、中、尾的中位数）、随机基准，避免最坏情况
  • 小规模子数组：递归到一定长度（如 ）改用插入排序，减少递归开销
  • 三路快排：将数组分为「小于基准、等于基准、大于基准」，优化重复元素多的场景

• 适用场景：大规模数据（工业界主流排序算法）、无稳定性要求的场景（如常规数值排序）

2.2 插入类排序：将元素插入已排序区间实现有序

核心逻辑：将数组分为「已排序区」和「未排序区」，逐个取未排序元素插入已排序区的正确位置。

2.2.1 插入排序（Insertion Sort）

• 原理：从第二个元素开始，将当前元素插入前面已排序的子数组中。

• 核心步骤：

  1. 已排序区初始为 arr[0]，未排序区从 arr[1] 开始
  2. 取未排序区首元素 curr = arr[i]，向前遍历已排序区
  3. 若已排序区元素 arr[j] > curr，将 arr[j] 后移一位
  4. 找到 curr 的正确位置，插入并扩大已排序区

• 特性：

  • 时间复杂度：最好 （近乎有序）、最坏 / 平均
  • 空间复杂度：（原地排序）
  • 稳定性：稳定（相等元素插入到后方，不改变相对位置）

• 适用场景：小规模数据、近乎有序的数据集（效率优于冒泡排序）

2.2.2 希尔排序（Shell Sort）

• 原理：插入排序的优化版 —— 先将数组按「步长 gap」分组，对每组做插入排序；逐步缩小 gap 至 1，最终整体插入排序。

• 核心步骤：

  1. 初始化步长 gap（如 n/2， 为数组长度）
  2. 按 gap 分组，对每组执行插入排序
  3. gap = gap/2，重复步骤 2
  4. 当 gap=1 时，数组已基本有序，最后一次插入排序效率极高

• 特性：

  • 时间复杂度：无精确值（依赖步长），平均约 ，优于插入排序
  • 空间复杂度：（原地排序）
  • 稳定性：不稳定（分组插入会打乱相等元素位置）

• 适用场景：中等规模数据，比插入 / 冒泡排序高效，实现简单

2.3 选择类排序：选择未排序区的极值放到已排序区

核心逻辑：每次从「未排序区」选最小（大）元素，放到已排序区末尾。

2.3.1 选择排序（Selection Sort）

• 原理：分已排序 / 未排序区，每次选未排序区最小值，交换到已排序区末尾。

• 核心步骤：

  1. 已排序区初始为空，未排序区为整个数组
  2. 遍历未排序区，找到最小值的索引 min_idx
  3. 交换 arr[min_idx] 和未排序区首元素，扩大已排序区
  4. 重复直到未排序区为空

• 特性：

  • 时间复杂度：最好 / 最坏 / 平均均为 （无论数据是否有序，都需遍历找极值）
  • 空间复杂度：（原地排序）
  • 稳定性：不稳定（交换会打乱相等元素位置，如 [2, 2, 1]，第一次交换 1 和第一个 2，两个 2 的位置颠倒）

• 适用场景：小规模数据、对效率要求低的场景（仅优点是实现最简单）

2.3.2 堆排序（Heap Sort）

• 原理：利用堆（完全二叉树）的特性 —— 大顶堆（父节点≥子节点）的堆顶是最大值，依次提取堆顶并调整堆，实现排序。

• 核心步骤：

  1. 构建大顶堆（从最后一个非叶子节点开始，向上调整堆）
  2. 交换堆顶（最大值）和数组末尾元素，缩小堆的范围（排除已排序的末尾）
  3. 对剩余堆执行「堆化」，恢复大顶堆特性
  4. 重复步骤 2-3，直到堆的大小为 1

• 特性：

  • 时间复杂度：最好 / 最坏 / 平均均为 （建堆 ，每次堆化 ，共 次）
  • 空间复杂度：（原地排序）
  • 稳定性：不稳定（堆化交换会打乱相等元素位置）

• 适用场景：大规模数据、需要稳定 时间复杂度的场景（如嵌入式系统，无递归栈开销）

2.4 归并类排序：分治合并实现有序

2.4.1 归并排序（Merge Sort）

• 原理：分治思想 —— 将数组拆分为两个子数组，递归排序子数组，再合并两个有序子数组为一个有序数组。

• 核心步骤：

  1. 拆分：将数组从中间分为 left 和 right 两个子数组
  2. 递归：分别对 left 和 right 排序
  3. 合并：创建临时数组，依次取 left 和 right 的最小元素放入，最终拷贝回原数组

• 特性：

  • 时间复杂度：最好 / 最坏 / 平均均为 （分治的固定复杂度）
  • 空间复杂度：（非原地排序，需临时数组）
  • 稳定性：稳定（合并时相等元素优先取 left 的，保持相对位置）

• 优化技巧：

  • 小规模子数组改用插入排序
  • 原地归并：减少临时数组开销（实现复杂，实际较少用）
  • 外部排序：适合磁盘等外部存储的大数据排序（如数据库排序）

• 适用场景：大规模数据、需要稳定排序的场景（如对象排序，按某个字段排序且保留原顺序）

2.5 线性时间排序：仅限特定条件

这类算法突破 的下界，但仅适用于「数据范围有限」的场景（如整数、且值域已知）。

2.5.1 计数排序（Counting Sort）

• 原理：统计每个值的出现次数，再根据次数重构有序数组。

• 适用条件：数据为整数，且值域范围 较小（如 0~100）。

• 特性：

  • 时间复杂度：
  • 空间复杂度：
  • 稳定性：稳定

• 场景：成绩排序（0~100）、年龄排序（0~120）等值域小的整数排序。

2.5.2 基数排序（Radix Sort）

• 原理：按数字的每一位（个位、十位、百位…）依次排序（用计数 / 桶排序实现），从低位到高位。

• 适用条件：数据为整数 / 字符串，位数固定。

• 特性：

  • 时间复杂度：（ 为位数， 为每一位的取值范围）
  • 空间复杂度：
  • 稳定性：稳定

• 场景：手机号排序、身份证号排序、整数序列排序（位数少）

2.5.3 桶排序（Bucket Sort）

• 原理：将数据分到多个桶中，每个桶内单独排序（如插入排序），最后合并所有桶。

• 适用条件：数据分布均匀（如 0~1 之间的浮点数）。

• 特性：

  • 时间复杂度：（分布均匀时）
  • 空间复杂度：（ 为桶数）
  • 稳定性：稳定

• 场景：浮点数排序、均匀分布的整数排序

3. 主流排序算法对比总结

算法	时间复杂度（平均）	时间复杂度（最坏）	空间复杂度	稳定性	核心适用场景
冒泡排序				稳定	小规模、近乎有序数据
快速排序				不稳定	大规模数据、无稳定性要求
插入排序				稳定	小规模、近乎有序数据
希尔排序				不稳定	中等规模数据
选择排序				不稳定	小规模、实现简单优先
堆排序				不稳定	大规模、需稳定 时间
归并排序				稳定	大规模、需要稳定排序
计数排序				稳定	值域小的整数排序
基数排序				稳定	位数固定的整数 / 字符串排序
桶排序				稳定	分布均匀的浮点数 / 整数排序

4. 实践选型建议

• 常规业务场景（如后台数据排序）：优先选快速排序（优化版），兼顾效率和空间
• 需要稳定排序（如对象按字段排序）：选归并排序，或基数 / 计数 / 桶排序（符合条件时）
• 嵌入式 / 内存受限场景：选堆排序（原地 ），避免归并排序的额外空间
• 小规模 / 近乎有序数据：选插入排序（效率高于冒泡 / 选择）
• 特殊数据类型（如手机号、浮点数）：选基数排序 / 桶排序（匹配数据特性）

教学辅助视频

》十大排序算法讲解视频