排序算法对比与性能实测

2026 大纲 七（十二）排序算法的分析与应用 · 横向对比与选型部分（中间状态反推见《由中间状态反推排序算法》）。

这张表应该推得出来，而不是记住

下面那张总表里的每一格，都能从对应单篇的推导重新算出来。硬记的表一旦记混就没有自查手段，而推得出来的表记混了自己就能发现。

所以看表的方式是：先遮住某一格，问自己"这个算法一趟干了什么、它的开销来自哪里"，再对答案。忘了哪一格怎么来的，点链接回去看。

算法	最好时间	平均时间	最坏时间	空间	稳定性	推导在哪
直接插入排序	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	稳定	插入
折半插入排序	$O(n{\log }_{2}n)$	$O(n^2)$	$O(n^2)$	$O(1)$	稳定	折半插入
希尔排序	$\mathrm{\Theta }(n{\log }_{2}n)$	约 $O(n^{1.3})$	$O(n^2)$	$O(1)$	不稳定	希尔
冒泡（起泡）排序	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	稳定	冒泡
快速排序	$O(n{\log }_{2}n)$	$O(n{\log }_{2}n)$	$O(n^2)$	$O({\log }_{2}n)\sim O(n)$	不稳定	快排
简单选择排序	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	不稳定	简单选择
堆排序	$O(n{\log }_{2}n)$	$O(n{\log }_{2}n)$	$O(n{\log }_{2}n)$	$O(1)$	不稳定	堆排序
二路归并排序	$O(n{\log }_{2}n)$	$O(n{\log }_{2}n)$	$O(n{\log }_{2}n)$	$O(n)$	稳定	归并
基数排序（非比较）	$O(d(n+r))$	$O(d(n+r))$	$O(d(n+r))$	$O(r)$；链式 $O(n+r)$	稳定	基数

$d$ = 关键字位数，$r$ = 基数（十进制 $r=10$）。

表里有六格需要限定条件，不加限定就是错的：

• 直接插入、冒泡的最好 $O(n)$：分别在"正序 + 内层循环不执行"和"正序 + 带提前终止标志"时取到。冒泡若不带 swapped 标志，最好也是 $O(n^2)$。
• 折半插入的最好是 $O(n{\log }_{2}n)$ 而不是 $O(n)$：即使输入已有序，每趟的折半查找一次也省不掉。
• 希尔的最好与最坏都是针对 Shell 原始增量（$n/2,n/4,\dots ,1$）；换 Hibbard 增量最坏可压到 $O(n^{1.5})$。谈希尔的复杂度必须先说清用的是哪个增量序列。
• 快排的空间不是 $O(1)$：没有辅助数组，但有递归栈，深度 = 递归树高。
• 简单选择排序没有"最好情况"：比较次数恒为 $n(n-1)/2$，三种情况完全一样。
• 基数排序的适用条件：关键字可拆成 $d$ 位、每位 $r$ 种取值，且主次关系与取值范围已知。

先动手看一眼

加载可视化中...

五组必须记准的横向结论

① 稳定性：快选希堆不稳定，其余全稳定。

四个不稳定的算法都存在同一个动作：元素一步越过与它相等、却从未与它直接比较过的元素。

算法	反例	那一步动作
快速排序	{3a, 3b, 2}	枢轴从区间一端被直接搬到分界处
简单选择排序	{2a, 2b, 1}	a[i] 与远处的 a[k] 整体交换
希尔排序	{2a, 2b, 1, 3}	相等元素被分到不同组，各组独立排序时互相看不见
堆排序	{21, 25, 49, 25*, 16, 08}	堆顶与末元素交换，随后的筛选又把元素沿路径搬运

反过来，四个稳定的比较排序，稳定性各自落在一个比较符号上：插入的 A[j] > temp（相等即停）、折半插入的 low = mid + 1（相等往右找）、冒泡的 a[j] > a[j+1]（相等不换）、归并的 B[i] <= B[j]（相等取左段）。改一个符号，对应算法立刻不稳定。

② 每趟至少确定一个元素最终位置的：简单选择、快排、堆排（冒泡也符合）。

判据是"这一趟有没有看过全局"。插入、希尔、归并、基数都不符合——它们每趟只看过局部（前 $i$ 个／组内／段内／一位）。

③ 趟数随输入变的只有两个：冒泡（$1\sim n-1$，已有序时 1 趟终止）、快排（= 递归深度）。其余六个由 $n$、$d$、$t$ 唯一确定。

④ 不能用于链表的四个：折半插入、希尔、快排、堆排——它们都要按下标随机存取。链表上要做 $O(n\log n)$ 排序，唯一现实的选择是二路归并。

⑤ 两个"唯一"别串：

归并排序：唯一既稳定、又保证最坏 $O(n{\log }_{2}n)$ 的比较排序，代价是 $O(n)$ 辅助空间。 堆排序：唯一既空间 $O(1)$、又保证最坏 $O(n{\log }_{2}n)$ 的比较排序，代价是不稳定。

谁的次数与输入无关：这一组最容易记反

算法	比较次数	移动次数
简单选择	无关（恒 $n(n-1)/2$）	有关（0 ～ $3(n-1)$）
折半插入	几乎无关（恒 $\mathrm{\Theta }(n{\log }_{2}n)$）	有关（= 逆序对数）
二路归并	有关（每趟在 $n/2$ 与 $n-1$ 之间）	无关（每趟恒 $n$）
基数排序	不做关键字比较	无关（每趟每个元素各分配一次）
堆排序	与输入弱相关，量级恒为 $O(n{\log }_{2}n)$	同左
直接插入 / 冒泡 / 快排	有关	有关

🔴 简单选择与二路归并恰好相反——前者比较无关、移动有关，后者移动无关、比较有关。放一起记，就不会串。

真题问过"元素的移动次数与关键字的初始排列次序无关的是"，候选是直接插入、冒泡、基数、快速，答案是基数排序。⚠️ 别顺手选简单选择——它只有比较次数无关。

具体的次数公式（$O(n^2)$ 那三个）：

算法	比较次数（最好）	比较次数（最坏）	移动次数（最好）	移动次数（最坏）
直接插入	$n-1$	${\displaystyle \frac{(n+2)(n-1)}{2}}$	0	${\displaystyle \frac{(n+4)(n-1)}{2}}$
冒泡排序	$n-1$	${\displaystyle \frac{n(n-1)}{2}}$	0	${\displaystyle \frac{3n(n-1)}{2}}$
简单选择	${\displaystyle \frac{n(n-1)}{2}}$	${\displaystyle \frac{n(n-1)}{2}}$	0	$3(n-1)$

三条读数：简单选择的比较次数恒定（双重循环边界只含下标）；它的移动次数是 $O(n)$，比另两个低整整一个数量级，记录很大时反而最划算；冒泡的移动次数正好是直接插入的 3 倍（两者"该动几次"都等于逆序对数，但冒泡一次交换写 3 条赋值、插入一次后移只写 1 条）。

选型：五个因素、一张决策图

选排序算法要综合考虑：待排序的记录个数、记录本身的大小、关键字的结构及初始状态、对稳定性的要求、存储结构。

真题正面问过"选择排序算法时，除时空效率外还需要考虑什么"，四个候选是数据规模、数据的存储方式、算法的稳定性、数据的初始状态——四条全都要考虑。

按约束逐条对照的理由，以及简单算法与先进算法的组合（决策图看不出理由时展开）

约束	推荐	理由
$n$ 很小（几十以内）	直接插入排序	$n^2$ 与 $n{\log }_{2}n$ 差别不大，简单算法的常数因子更小、无递归开销
初始基本有序	直接插入排序	后移次数 = 逆序对数，逆序对少则内层几乎不执行，接近 $O(n)$。⚠️ 此时绝不要用取首元素为枢轴的快排，那是它的最坏情形
$n$ 大、关键字随机、不要求稳定	快速排序	平均 $O(n{\log }_{2}n)$ 且常数因子最小
要求最坏也是 $O(n{\log }_{2}n)$	堆排序 或 二路归并排序	两者都不会退化；堆排空间 $O(1)$，归并要 $O(n)$
内存紧张 + 要最坏保证	堆排序	唯一同时做到"最坏 $O(n{\log }_{2}n)$"与"空间 $O(1)$"的
要求稳定 + 要最坏保证	二路归并排序	唯一既稳定又保证最坏 $O(n{\log }_{2}n)$ 的比较排序
记录很大（移动代价高）	简单选择排序（$n$ 小时）；或对索引/指针排序（$n$ 大时）	简单选择的移动次数只有 $O(n)$；对指针排序则把移动代价降到与记录大小无关
关键字位数少、取值范围已知、$n$ 很大	基数排序	$O(d(n+r))$ 可近似线性；但 $d$ 大或 $r\gg n$ 时反而更慢
链式存储	直接插入（$n$ 小）或二路归并（$n$ 大）	其余算法要么需要随机存取，要么在链表上收益归零
数据量超出内存	外部排序	优化目标从"比较+移动"换成"I/O 趟数"

组合使用：

• 快排 + 直接插入：递归到子区间长度小于某个阈值时改调直接插入排序——小规模下它的常数因子更小，还省掉了递归开销。
• 分段插入 + 归并：$n$ 很大时先把序列划分成若干子序列分别做直接插入排序，再用归并把有序子序列合并起来。
• MSD 基数 + 直接插入：关键字很大但大多数记录的最高位互不相同时，先按最高位分成若干小子序列，再各自用直接插入排序。

空间来源、趟数、链表适用的完整对照（要逐维核对就展开）

空间复杂度的三种来源。

空间复杂度	算法	来源
$O(1)$	直接插入、折半插入、冒泡、简单选择、希尔、堆排序	只有暂存一条记录的辅助单元
$O({\log }_{2}n)\sim O(n)$	快速排序	递归栈，深度 = 递归树高
$O(n)$	二路归并排序	辅助数组 $O(n)$ + 递归栈 $O({\log }_{2}n)$，由前者主导
$O(r)$ 或 $O(n+r)$	基数排序	$r$ 个队列的头尾指针；链式实现还要加 $n$ 个指针域

辅助空间只有三种来源：暂存单元、递归栈、辅助数组／队列。递归栈必须计入——这是快排空间被写成 $O(1)$ 的常见错误来源。归并排序在链表上归并只需改指针、不需要辅助数组，空间可从 $O(n)$ 降到 $O({\log }_{2}n)$。

趟数与初始序列的关系。

算法	趟数	是否随初始序列变
直接插入 / 折半插入	$n-1$	否
简单选择	$n-1$	否
堆排序	$n-1$（建初堆不计入）	否
二路归并	$\lceil {\log }_{2}n\rceil$	否
基数排序	$d$	否
希尔排序	增量序列长度 $t$	否（但 $t$ 由所选增量序列决定）
冒泡排序	$1\sim n-1$	是——已有序时 1 趟即终止
快速排序	= 递归树深度	是——划分是否均匀完全取决于数据

能否用于链式存储。

可用于链表	不可用于链表	判据
直接插入（且不用移动记录）、冒泡、简单选择、二路归并（且不用辅助数组）、基数排序	折半插入、希尔、快速排序、堆排序	算法是否依赖按下标随机存取：折半查找要取中点、希尔要跳 $d$ 格、快排要双向扫描并定位上下界、堆排要用下标算术定位父子

比较类排序的下界，以及它解释了总表里的什么

任何基于关键字比较的排序算法，最坏情况下至少需要 $\mathrm{\Omega }(n{\log }_{2}n)$ 次比较。思路是把执行过程画成判定树（每次比较两种结果 $\Rightarrow$ 二叉树），叶结点要覆盖全部 $n!$ 种排列，故 $2^h\ge n!$，$h\ge {\log }_2(n!)=\mathrm{\Theta }(n{\log }_{2}n)$。完整推导与三条适用边界见排序的基本概念。

这条下界解释了总表里的两件事：

1. 没有任何比较类排序的最坏情况能优于 $O(n{\log }_{2}n)$——归并与堆排已经触底，无法再改进。
2. 基数排序能做到 $O(d(n+r))$，是因为它的信息来源不是"两两比较的结果"而是关键字自身的取值（用值去索引桶），下界的前提不成立。

实测性能曲线

加载可视化中...

曲线里该看出什么：五组实验的读数（想把结论看成一条曲线就展开）

理论复杂度是渐进分析，实际耗时还取决于常数因子和数据分布。上面的工具在浏览器中实时运行七种排序，从 $n=50$ 到 $n=50000$，绘制耗时、比较次数、交换次数的增长曲线，可切换数据分布（随机、已排序、逆序、基本有序）。

实验一：随机数据 + 耗时。 $O(n^2)$ 一族（冒泡、选择、插入）与 $O(n\log n)$ 一族（快排、归并、堆排）明显分离——前者呈抛物线增长，后者几乎是一条平线。同一次运行里 $n=50000$ 时冒泡约 4275 ms、快排仅 5.5 ms，相差约 777 倍。

实验二：已排序数据 + 耗时。 插入与冒泡降到 $O(n)$，耗时骤降到 1 ms 以内；但选择排序仍然超过 1 秒——它的比较次数恒为 $n(n-1)/2$，与数据是否有序无关。$n=50000$ 时这个数是约 12.5 亿次。这一组把"基本有序序列用直接插入排序"从一句结论变成了一条能看见的曲线。

实验三：随机数据 + 交换／移动次数。 冒泡与插入的交换／移动次数在数量级上相同（都约 6.2 亿次，正是随机序列逆序对数的期望 $\frac{n(n-1)}{4}$），但插入排序的实际耗时只有冒泡的约五分之一——原因正是"一次交换 = 3 条赋值，一次后移 = 1 条赋值"。

实验四：已排序数据 + 交换／移动次数。 冒泡、插入、选择、希尔的交换／移动次数全部为 0（已有序，没有任何逆序对要消），但选择排序依然很慢——因为它照样做了约 12.5 亿次比较。这直观说明比较次数与移动次数对性能的影响是彼此独立的两项，必须分开数。

实验五：逆序数据 + 耗时。 冒泡与插入都退化到各自的 $O(n^2)$ 最坏值；而 $O(n\log n)$ 一族不受影响——这就是"最坏情况保证"的含义。顺带留意快排在已排序与逆序两组数据上的表现。

三组数字彼此印证：比较次数 $\frac{n(n-1)}{2}\approx 12.5$ 亿、逆序对期望 $\frac{n(n-1)}{4}\approx 6.25$ 亿、耗时比 $4275/5.5\approx 777$。读曲线时可拿这三个数当锚点核对。

考点速记

三条结论：

1. 稳定性口诀"快选希堆不稳定"；四个不稳定的都存在"越过从未与之比较的相等元素"这个动作。
2. 简单选择的比较次数与输入无关、二路归并的移动次数与输入无关——两者恰好相反，放一起记。
3. 两个"唯一"：归并是唯一"稳定 + 最坏有保证"的，堆排是唯一"空间 $O(1)$ + 最坏有保证"的。

这一节在真题里被考过的形式（下方「真题练习」与《由中间状态反推排序算法》《排序的基本概念》共用同一批题）：

• 哪些排序算法不稳定：五个候选（希尔、归并、快排、堆排、基数）里挑，答希尔、快排、堆排三个。归并与基数都稳定。
• 每一趟结束都至少能确定一个元素最终位置的有哪些：五个候选（简单选择、希尔、快排、堆排、二路归并）里答简单选择、快排、堆排。希尔与归并都不符合。
• 选择排序算法时除时空效率外还需考虑什么：数据规模、数据的存储方式、算法的稳定性、数据的初始状态——四条全要考虑。
• 给一段代码问输出、比较次数与稳定性（大题）：题面给的是教材版计数排序 cmpCountSort（对每个元素数有多少比它小）。三问依次答：模拟出的输出数组、$\frac{n(n-1)}{2}$、不稳定且改法是把 a[i] < a[j] 改成 a[i] <= a[j]（详见计数排序）。
• 用直插不用快排的原因：大部分已有序、元素很少、要求空间 $O(1)$、要求稳定——四条全对。

易错：归并排序稳定，基数排序也稳定。 不稳定的只有快、选、希、堆四个。

易错：归并排序每趟 0 个元素就位。 "每趟至少确定一个"的题里它是被排除的那个。

易错：快排的空间不是 $O(1)$，递归栈平均 $O({\log }_{2}n)$、最坏 $O(n)$。

教材出处

• 各种内部排序方法的比较（表 8.2，含九种算法的最好／最坏／平均时间复杂度、空间复杂度与稳定性）：严蔚敏《数据结构（C 语言版）》（第 2 版），p267
• 选用排序方法需综合考虑的五个因素（待排序记录个数、记录本身大小、关键字的结构及初始状态、对稳定性的要求、存储结构）与四条结论（$n$ 小时选简单方法且基本有序时直接插入最佳；$n$ 大时随机分布选快排、基本有序选堆排、要求稳定选归并；简单方法与先进方法可组合使用；基数排序适用于 $n$ 很大而关键字较小的序列）：同书 p268
• "直接插入排序、归并排序都易于在链表上实现。但像折半插入排序、希尔排序、快速排序和堆排序，却难于在链表上实现"：同书 p269
• 各算法单项结论的出处见各自单篇的「教材出处」一节

相关知识

排序的基本概念（稳定性定义、下界的完整推导）｜ 由中间状态反推排序算法（本条目的另一半）｜ 外部排序｜ 直接插入｜折半插入｜希尔｜冒泡｜快排｜简单选择｜堆排序｜归并｜基数｜ 计数排序（不在大纲内，作为基数排序的前置理解保留）

相关文章

• 排序基本概念
• 直接插入排序
• 折半插入排序
• 希尔排序
• 冒泡排序
• 快速排序
• 简单选择排序
• 堆排序
• 归并排序
• 基数排序
• 计数排序
• 外部排序
• 由中间状态反推排序算法

真题练习

相关真题（5题）

2023Q102分2022Q112分2021Q428分2019Q72分2012Q102分