各种排序算法的比较

1. 排序算法综合对比表

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

2. 按时间复杂度分类

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

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

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

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

  • 快速排序(平均)
  • 堆排序
  • 归并排序
  • 希尔排序(平均)

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

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

  • 基数排序(当 dd 和 rr 为常数时)
  • 计数排序
  • 桶排序

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

3. 按稳定性分类

3.1 稳定排序

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

3.2 不稳定排序

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

4. 按空间复杂度分类

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

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

4.2 非原地排序

  • 归并排序:O(n)O(n)
  • 基数排序:O(n+r)O(n+r)
  • 计数排序:O(n+k)O(n+k)
  • 桶排序:O(n+k)O(n+k)

5. 排序算法的选择

选择排序算法时,需要考虑以下因素:

5.1 数据规模

  • 小规模数据(n<50n < 50):直接插入排序或简单选择排序,实现简单且常数因子小
  • 中规模数据(50<n<1000050 < n < 10000):希尔排序或快速排序
  • 大规模数据(n>10000n > 10000):快速排序、归并排序或堆排序

5.2 数据初始状态

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

5.3 稳定性要求

  • 需要稳定排序:归并排序(高效且稳定)、插入排序(小规模)、冒泡排序(小规模)、基数排序
  • 不需要稳定排序:快速排序、堆排序(效率更高)

5.4 内存限制

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

5.5 关键字类型

  • 整数且范围有限:计数排序或基数排序(O(n)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(nlog⁡n)O(n \log n) 且稳定的是( )

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

排序算法比较稳定性时间复杂度归并排序

解题思路:

本题考查排序算法的稳定性与平均时间复杂度。题干给出两个限定条件——平均时间复杂度为 O(nlog⁡n)O(n \log n) 且稳定——需要把四个算法逐一对照这两条要求来筛选。

详细步骤:

  1. 快速排序:平均 O(nlog⁡n)O(n \log n),但不稳定
  2. 堆排序:平均 O(nlog⁡n)O(n \log n),但不稳定
  3. 归并排序:平均 O(nlog⁡n)O(n \log n),且稳定
  4. 希尔排序:平均约 O(n1.3)O(n^{1.3}),且不稳定
  5. 只有归并排序同时满足“平均 O(nlog⁡n)O(n \log n)”与“稳定”这两个条件。

最终答案:

C。

习题 2

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

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

排序算法比较最坏情况比较次数堆排序

解题思路:

本题考查四个排序算法在最坏情况下的比较次数。关键是比较时间复杂度的量级:前三个算法最坏都是 O(n2)O(n^2),比较次数达到 n(n−1)2\frac{n(n-1)}{2};而堆排序最坏只有 O(nlog⁡n)O(n \log n),比较次数更少。

详细步骤:

  1. 直接插入排序:最坏比较次数 n(n−1)2=28\frac{n(n-1)}{2} = 28
  2. 冒泡排序:最坏比较次数 n(n−1)2=28\frac{n(n-1)}{2} = 28
  3. 简单选择排序:比较次数恒为 n(n−1)2=28\frac{n(n-1)}{2} = 28
  4. 堆排序:最坏比较次数约为 nlog⁡2n≈8×3=24n \log_2 n \approx 8 \times 3 = 24
  5. 堆排序的最坏时间复杂度为 O(nlog⁡n)O(n \log n),比其他三个 O(n2)O(n^2) 的算法比较次数少。

最终答案:

D。

简答题

习题 3

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

排序算法比较快速排序堆排序归并排序

解题思路:

本题考查快速排序、堆排序与归并排序的优缺点及适用场景。答题时按“优点—缺点—适用场景”三个维度分别评述三种算法,最后按不同需求给出选择建议。

详细步骤:

  1. 快速排序——优点:平均时间复杂度 O(nlog⁡n)O(n \log n),常数因子最小,实际运行效率最高;原地排序(递归栈 O(log⁡n)O(\log n));缓存友好,局部性好。缺点:最坏情况 O(n2)O(n^2)(数据已有序或基本有序,需优化基准选择);不稳定排序;递归实现有栈溢出风险。适用场景:大规模随机数据;对稳定性没有要求;内存有限;实际应用中最常用的排序算法。
  2. 堆排序——优点:时间复杂度恒为 O(nlog⁡n)O(n \log n),性能稳定;原地排序,空间复杂度 O(1)O(1);适合实现优先队列。缺点:不稳定排序;常数因子比快速排序大;缓存不友好(跳跃式访问数组)。适用场景:对时间复杂度稳定性要求高的场景;内存有限;需要优先队列的场景(如 Top K 问题、Dijkstra 算法、任务调度)。
  3. 归并排序——优点:时间复杂度恒为 O(nlog⁡n)O(n \log n),性能稳定;稳定排序;适合链表排序(不需要额外数组空间);适合外部排序。缺点:空间复杂度 O(n)O(n),需要额外辅助数组;常数因子比快速排序大;不是原地排序(标准实现)。适用场景:对稳定性有要求的场景;链表排序;外部排序(数据量大,内存不足);数据量较大且需要稳定性能的场景。
  4. 选择建议——追求最高平均性能、不要求稳定时选快速排序;要求性能稳定、内存有限且不要求稳定时选堆排序;要求稳定,或链表排序,或外部排序时选归并排序。实际应用中,大多数语言的标准库使用混合排序算法(如 Introsort、Timsort),结合了多种排序算法的优点。

最终答案:

快速排序平均性能最好但最坏可达 O(n2)O(n^2) 且不稳定;堆排序时间复杂度恒为 O(nlog⁡n)O(n \log n)、空间 O(1)O(1) 但不稳定且缓存不友好;归并排序稳定、时间恒为 O(nlog⁡n)O(n \log n) 但需 O(n)O(n) 辅助空间,适合链表与外部排序。

发现内容有问题?

告诉我们哪里需要改进。