排序算法可视化对比

冒泡、选择、插入、归并、快排、堆排序——六种最经典的排序算法，用同一根柱子、同一个计数器来赛跑。 亲手拖动滑块、切换算法，看它们的比较次数与交换次数如何随规模增长而分道扬镳。

冒泡排序 O(n²) 选择排序 O(n²) 插入排序 O(n²) 归并排序 O(n log n) 快速排序 O(n log n) 堆排序 O(n log n)

1公式与参数

排序算法的代价由两个量刻画：比较次数（$C$，元素之间比大小的次数）与 交换/写入次数（$S$，元素位置的改动次数）。 在最坏情况下，它们的增长率决定了算法能不能扛住大规模数据。

$$C_{\text{冒泡}} = \sum_{i=1}^{n-1}(n-i) = \frac{n(n-1)}{2} = \Theta(n^2)$$
$$C_{\text{选择}} = \frac{n(n-1)}{2}, \qquad S_{\text{选择}} \le n-1$$

插入排序在最坏情况下比较次数与冒泡相同，但最好情况下只需线性时间—— 这正是它成为小规模数据首选的原因。

$$C_{\text{插入}}^{\text{最坏}} = \frac{n(n-1)}{2}, \qquad C_{\text{插入}}^{\text{最好}} = n-1 = \Theta(n)$$

归并排序与快速排序都属于分治算法，其时间由主定理（Master Theorem）刻画。 对于形如 $T(n) = aT(n/b) + f(n)$ 的递推：

$$T(n) = a\,T\!\left(\frac{n}{b}\right) + f(n), \qquad \text{若 } f(n) = \Theta\!\left(n^{\log_b a}\right) \text{ 则 } T(n) = \Theta\!\left(n^{\log_b a}\log n\right)$$

归并排序把问题一分为二，每层合并代价为 $\Theta(n)$；快速排序的分割点依赖于枢轴， 平均情况下也达到 $O(n \log n)$，但最坏情况会退化为 $O(n^2)$：

$$T_{\text{归并}}(n) = 2T\!\left(\tfrac{n}{2}\right) + \Theta(n) = \Theta(n \log n)$$
$$T_{\text{快排}}(n) = T(k) + T(n-1-k) + \Theta(n), \quad \text{平均 } \Theta(n\log n)$$

堆排序先在线性时间内建堆，再反复取出堆顶：

$$T_{\text{堆}}(n) = \underbrace{\Theta(n)}_{\text{建堆}} + \sum_{i=n}^{2} \underbrace{\Theta(\log i)}_{\text{调整堆}} = \Theta(n \log n)$$

最后，任何基于比较的排序算法都有理论下界——这是信息论给出的天花板：

$$\forall \text{ 比较排序 } A, \quad T_A(n) = \Omega(n \log n)$$

直观理解：$n$ 个元素有 $n!$ 种排列，每次比较最多提供 1 bit 信息，至少需要 $\log_2(n!) = \Theta(n \log n)$ 次比较才能区分所有可能。

符号 数学含义 通俗解释
n 数组长度 / 问题规模 待排序元素的个数。本页可调范围 10~40。$n$ 翻倍时，$O(n^2)$ 算法耗时约 4 倍，$O(n\log n)$ 算法约 2.2 倍。
C 比较次数 执行了多少次"比大小"。这是排序算法的核心开销。
S 交换 / 写入次数 元素位置改动了多少次。对写代价高昂的存储（如闪存）尤其重要。
T(n) 时间复杂度 运行时间随 $n$ 增长的量级。$\Theta(n^2)$ 意味着规模翻倍时间变 4 倍。
Θ / O / Ω 渐进记号 $\Theta$ 是紧确界，$O$ 是上界，$\Omega$ 是下界。工程上常混用 $O$ 表示上界。
稳定性 相等元素相对次序是否保持 若两个元素相等，排序后它们的先后顺序不变，则称算法稳定。归并、插入、冒泡稳定；选择、快排、堆排不稳定。
原地 额外空间 $O(1)$ 原地排序只用常数级额外内存。冒泡、选择、插入、快排、堆排是原地；归并需要 $O(n)$ 辅助数组。

2交互模拟：柱状图上的算法赛跑

左侧选择算法、调整数组规模与播放速度，右侧柱状图会实时展示每一步的比较（黄色）、 交换/写入（红色）与已就位（绿色）状态。 上方的计数器会精确记录每一次操作——切换算法重跑同一组数据，差距立刻显现。

元素越多，$O(n^2)$ 与 $O(n\log n)$ 的差距越明显。
值越小动画越慢，能看清每一步；值越大越快看到最终结果。
换一种初始形态，插入排序与快速排序的表现会截然不同。
比较次数
0
交换 / 写入
0
进度
0.00%
总步数
0
待运行
未处理 正在比较 正在交换/写入 已就位
等待开始…

3复杂度对比与深入理解

下图用对数坐标对比了六种算法的比较次数随规模增长的曲线。注意 $O(n^2)$ 与 $O(n\log n)$ 在 $n$ 较小时差距不明显，但随着规模增大，指数级差距会迅速拉开。

标准介绍

排序是计算机科学中最基础、研究最透彻的问题之一。基于比较的排序算法， 其时间复杂度下界由决策树模型证明为 $\Omega(n\log n)$——这意味归并排序和堆排序已经是 渐进最优的。冒泡、选择、插入属于 $O(n^2)$ 的初级算法， 实现简单但在大规模数据上不可用。快速排序由 Hoare 于 1960 年提出， 以极佳的常数因子和缓存局部性成为实践中最常用的通用排序，工业实现（如 C++ 的 std::sort）通常采用内省排序（Introsort），在快排退化时切换到堆排序。

通俗介绍

把排序想象成整理一副扑克牌。 冒泡是反复从头到尾两两比较，把大的往后推——像气泡往上浮，一趟下来最大的就到了末尾。 选择是每轮从未排区间里挑出最小的，放到已排区的后面——像选秀挑人。 插入是像打牌时摸到一张新牌，从右往左比，找到合适位置插进去——手里始终保持有序。 归并是把牌分成两堆，各自排好，再像拉链一样合并起来。 快排是随便抽一张牌当基准，比它小的放左边，大的放右边，然后对两边递归。 堆排序是先把牌搭成一个大顶堆（最大值始终在顶端），再把顶端抽走放到末尾，重新调整堆。

解决了什么问题

  • 为"把无序变有序"提供了可证明正确的系统化方法，是所有数据处理的前置步骤。
  • 建立了比较排序的理论下界 $\Omega(n\log n)$，明确了"不可能更快"的边界。
  • 展示了分治思想（归并、快排）与数据结构驱动（堆）两类经典范式。
  • 揭示了平均情况与最坏情况的差异：快排平均最优但最坏退化，堆排序则始终稳定。
  • 提供了稳定性 / 原地性 / 适应性等工程权衡维度，指导实际选型。

为什么重要

  • 它是算法分析与设计的入门典范：渐进记号、递推式、主定理、下界证明都在这里首次登场。
  • 它是实际系统的性能瓶颈之一：数据库索引、搜索引擎、日志分析都依赖高效排序。
  • 它是语言标准库的核心组件：std::sort、 Arrays.sort、sorted() 每天都在被亿万个程序调用。
  • 它教会工程师不要过早优化，也不要盲目优化：$n$ 很小时插入排序往往比快排更快。

应用场景

  • 数据库：ORDER BY、索引构建、归并连接（Merge Join）大量使用归并排序。
  • 标准库：C++ 用 Introsort，Java 用 TimSort（归并+插入的混合），Python 用 TimSort。
  • 外部排序：数据量超过内存时，多路归并排序是唯一可行的方案。
  • 实时系统：堆排序因最坏情况也保证 $O(n\log n)$，适合硬实时场景。
  • 嵌入式：插入排序因代码短、常数小，常用于小数组或中断上下文。
  • 数据分析：Top-K 问题用堆排序思想维护固定大小的堆，避免全排序。

缺陷与局限

  • 没有任何一种排序在所有场景都最优：快排常数小但最坏退化，归并稳定但费内存。
  • 比较排序无法突破 $\Omega(n\log n)$：想更快只能放弃"通用比较"假设。
  • 快排的最坏情况可被构造攻击：恶意输入能让它退化为 $O(n^2)$，需用随机化或内省法防御。
  • 归并排序的额外空间在内存受限场景下是硬伤，虽然可以原地归并但常数极大。
  • 稳定性与原地性往往不可兼得：需要稳定且原地时，选择非常有限（如插入排序）。
  • 计数/基数排序虽然能到线性，但仅适用于整数或有限键空间，通用性不足。

动手建议

把数组规模固定为 n=30，初始形态选"随机乱序"， 依次跑一遍六种算法，把比较次数记下来： 冒泡和选择都接近 $n(n-1)/2 = 435$；插入大约 200 出头；而归并、快排、堆排序都只在 100 上下。 然后把初始形态切到"几乎有序"再跑一次： 插入排序的比较次数会骤降到接近 $n$，而选择排序纹丝不动（它总是要扫描整个未排区间）。 最后切到"完全逆序"：快速排序如果固定取末尾元素为枢轴，会退化成 $O(n^2)$， 比较次数飙升——这正是工业实现要随机化枢轴的原因。