各种排序算法的比较

本章节对各种内部排序算法进行综合对比，帮助你在实际应用中根据数据规模、数据特点、稳定性要求等因素选择最合适的排序算法。没有”最好”的排序算法，只有”最合适”的排序算法。

1. 排序算法综合对比表

算法	最好时间	平均时间	最坏时间	空间复杂度	稳定性	排序方式
直接插入排序	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	稳定	插入
折半插入排序	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	稳定	插入
希尔排序	$O(n)$	$O(n^{1.3})$	$O(n^2)$	$O(1)$	不稳定	插入
冒泡排序	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	稳定	交换
快速排序	$O(n\log n)$	$O(n\log n)$	$O(n^2)$	$O(\log n)$	不稳定	交换
简单选择排序	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	不稳定	选择
堆排序	$O(n\log n)$	$O(n\log n)$	$O(n\log n)$	$O(1)$	不稳定	选择
归并排序	$O(n\log n)$	$O(n\log n)$	$O(n\log n)$	$O(n)$	稳定	归并
基数排序	$O(d(n+r))$	$O(d(n+r))$	$O(d(n+r))$	$O(n+r)$	稳定	非比较

2. 按时间复杂度分类

2.1 $O(n^2)$ 级（简单排序）

直接插入排序
折半插入排序
冒泡排序
简单选择排序
希尔排序（最坏情况）
快速排序（最坏情况）

特点：实现简单，常数因子小，适合小规模数据。其中直接插入排序在数据基本有序时效率极高（ $O(n)$ ）。

2.2 $O(n \log n)$ 级（高效排序）

快速排序（平均）
堆排序
归并排序
希尔排序（平均）

特点：效率高，适合大规模数据。快速排序平均性能最好，堆排序性能稳定且原地排序，归并排序稳定且性能稳定。

2.3 $O(n)$ 级（非比较排序）

基数排序（当 $d$ 和 $r$ 为常数时）
计数排序
桶排序

特点：突破比较排序 $O(n \log n)$ 的下界，但有适用条件限制（关键字范围有限、位数较少等），且空间复杂度较高。

3. 按稳定性分类

3.1 稳定排序

直接插入排序
折半插入排序
冒泡排序
归并排序
基数排序

3.2 不稳定排序

希尔排序
快速排序
简单选择排序
堆排序

稳定性在多关键字排序中很重要。如果需要稳定排序，可以选择插入排序、冒泡排序、归并排序或基数排序。快速排序和堆排序虽然效率高，但不稳定。如果需要稳定且高效的排序，归并排序是最佳选择。

4. 按空间复杂度分类

4.1 原地排序（ $O(1)$ ）

直接插入排序
折半插入排序
希尔排序
冒泡排序
简单选择排序
堆排序
快速排序（递归栈 $O(\log n)$ ，但通常视为原地排序）

4.2 非原地排序

归并排序： $O(n)$
基数排序： $O(n+r)$
计数排序： $O(n+k)$
桶排序： $O(n+k)$

5. 排序算法的选择

选择排序算法时，需要考虑以下因素：

5.1 数据规模

小规模数据（ $n < 50$ ）：直接插入排序或简单选择排序，实现简单且常数因子小
中规模数据（ $50 < n < 10000$ ）：希尔排序或快速排序
大规模数据（ $n > 10000$ ）：快速排序、归并排序或堆排序

5.2 数据初始状态

数据基本有序：直接插入排序（最好 $O(n)$ ）或冒泡排序（优化版 $O(n)$ ）
数据完全逆序：避免使用快速排序（最坏 $O(n^2)$ ），选择堆排序或归并排序
数据随机分布：快速排序平均性能最好
大量重复元素：三路划分的快速排序

5.3 稳定性要求

需要稳定排序：归并排序（高效且稳定）、插入排序（小规模）、冒泡排序（小规模）、基数排序
不需要稳定排序：快速排序、堆排序（效率更高）

5.4 内存限制

内存有限：堆排序（原地 $O(1)$ ）、快速排序（原地）
内存充足：归并排序（需要 $O(n)$ 辅助空间，但稳定且高效）

5.5 关键字类型

整数且范围有限：计数排序或基数排序（ $O(n)$ ）
整数且位数较少：基数排序
浮点数或复杂对象：比较排序（快速、归并、堆）
字符串：基数排序（按字符）或比较排序

5.6 语言和库支持

大多数编程语言的标准库都提供了高效的排序函数：

C：qsort（快速排序）
C++：std::sort（快速排序+插入排序+堆排序的混合，称为Introsort）
Java：Arrays.sort（基本类型用快速排序，对象类型用归并排序/Timsort）
Python：sorted/list.sort（Timsort，归并排序+插入排序的混合）

6. 排序算法的发展趋势

混合排序：结合多种排序算法的优点，如Introsort（快速+堆+插入）、Timsort（归并+插入）
并行排序：利用多核CPU并行排序，如并行归并排序、并行快速排序
GPU排序：利用GPU的大规模并行能力进行排序
外部排序优化：针对SSD等新型存储设备优化外部排序算法
自适应排序：根据数据特点自动选择最优排序策略

习题

选择题

习题 1

以下排序算法中，平均时间复杂度为 $O(n \log n)$ 且稳定的是（）

A. 快速排序 B. 堆排序 C. 归并排序 D. 希尔排序

答案与解析

答案：C

解析：

快速排序：平均 $O(n \log n)$ ，但不稳定
堆排序：平均 $O(n \log n)$ ，但不稳定
归并排序：平均 $O(n \log n)$ ，且稳定
希尔排序：平均约 $O(n^{1.3})$ ，且不稳定

习题 2

对8个元素进行排序，以下排序算法中，最坏情况下比较次数最少的是（）

A. 直接插入排序 B. 冒泡排序 C. 简单选择排序 D. 堆排序

答案与解析

答案：D

解析：

直接插入排序：最坏比较次数 $\frac{n(n-1)}{2} = 28$
冒泡排序：最坏比较次数 $\frac{n(n-1)}{2} = 28$
简单选择排序：比较次数恒为 $\frac{n(n-1)}{2} = 28$
堆排序：最坏比较次数约为 $n \log_2 n \approx 8 \times 3 = 24$

堆排序的最坏时间复杂度为 $O(n \log n)$ ，比其他三个 $O(n^2)$ 的算法比较次数少。

简答题

习题 3

试比较快速排序、堆排序和归并排序的优缺点，并说明各自的适用场景。

答案与解析

快速排序：

优点：平均时间复杂度 $O(n \log n)$ ，常数因子最小，实际运行效率最高；原地排序（递归栈 $O(\log n)$ ）；缓存友好，局部性好
缺点：最坏情况 $O(n^2)$ （数据已有序或基本有序，需优化基准选择）；不稳定排序；递归实现有栈溢出风险
适用场景：大规模随机数据；对稳定性没有要求；内存有限；实际应用中最常用的排序算法

堆排序：

优点：时间复杂度恒为 $O(n \log n)$ ，性能稳定；原地排序，空间复杂度 $O(1)$ ；适合实现优先队列
缺点：不稳定排序；常数因子比快速排序大；缓存不友好（跳跃式访问数组）
适用场景：对时间复杂度稳定性要求高的场景；内存有限；需要优先队列的场景（如Top K问题、Dijkstra算法、任务调度）

归并排序：

优点：时间复杂度恒为 $O(n \log n)$ ，性能稳定；稳定排序；适合链表排序（不需要额外数组空间）；适合外部排序
缺点：空间复杂度 $O(n)$ ，需要额外辅助数组；常数因子比快速排序大；不是原地排序（标准实现）
适用场景：对稳定性有要求的场景；链表排序；外部排序（数据量大，内存不足）；数据量较大且需要稳定性能的场景

总结：

追求最高平均性能，不要求稳定 → 快速排序
要求性能稳定，内存有限，不要求稳定 → 堆排序
要求稳定，或链表排序，或外部排序 → 归并排序
实际应用中，大多数语言的标准库使用混合排序算法（如Introsort、Timsort），结合了多种排序算法的优点

上一章节排序的起源与实际意义介绍排序问题的历史、现实应用和产生动因。

下一章节插入排序介绍插入排序的基本思想、算法流程、复杂度分析及典型习题。

各种排序算法的比较

1. 排序算法综合对比表

2. 按时间复杂度分类

2.1 O(n2)O(n^2)O(n2) 级（简单排序）

2.2 O(nlog⁡n)O(n \log n)O(nlogn) 级（高效排序）

2.3 O(n)O(n)O(n) 级（非比较排序）

3. 按稳定性分类

3.1 稳定排序

3.2 不稳定排序

4. 按空间复杂度分类

4.1 原地排序（O(1)O(1)O(1)）

4.2 非原地排序

5. 排序算法的选择

5.1 数据规模

5.2 数据初始状态

5.3 稳定性要求

5.4 内存限制

5.5 关键字类型

5.6 语言和库支持

6. 排序算法的发展趋势

习题

选择题

习题 1

习题 2

简答题

习题 3

2.1 $O(n^2)$ 级（简单排序）

2.2 $O(n \log n)$ 级（高效排序）

2.3 $O(n)$ 级（非比较排序）

4.1 原地排序（ $O(1)$ ）