各种排序算法的比较
| 算法 | 最好时间 | 平均时间 | 最坏时间 | 空间复杂度 | 稳定性 | 排序方式 |
|---|---|---|---|---|---|---|
| 直接插入排序 | 稳定 | 插入 | ||||
| 折半插入排序 | 稳定 | 插入 | ||||
| 希尔排序 | 不稳定 | 插入 | ||||
| 冒泡排序 | 稳定 | 交换 | ||||
| 快速排序 | 不稳定 | 交换 | ||||
| 简单选择排序 | 不稳定 | 选择 | ||||
| 堆排序 | 不稳定 | 选择 | ||||
| 归并排序 | 稳定 | 归并 | ||||
| 基数排序 | 稳定 | 非比较 |
2.1 级(简单排序)
- 直接插入排序
- 折半插入排序
- 冒泡排序
- 简单选择排序
- 希尔排序(最坏情况)
- 快速排序(最坏情况)
特点:实现简单,常数因子小,适合小规模数据。其中直接插入排序在数据基本有序时效率极高()。
2.2 级(高效排序)
- 快速排序(平均)
- 堆排序
- 归并排序
- 希尔排序(平均)
特点:效率高,适合大规模数据。快速排序平均性能最好,堆排序性能稳定且原地排序,归并排序稳定且性能稳定。
2.3 级(非比较排序)
- 基数排序(当 和 为常数时)
- 计数排序
- 桶排序
特点:突破比较排序 的下界,但有适用条件限制(关键字范围有限、位数较少等),且空间复杂度较高。
3.1 稳定排序
- 直接插入排序
- 折半插入排序
- 冒泡排序
- 归并排序
- 基数排序
3.2 不稳定排序
- 希尔排序
- 快速排序
- 简单选择排序
- 堆排序
4.1 原地排序()
- 直接插入排序
- 折半插入排序
- 希尔排序
- 冒泡排序
- 简单选择排序
- 堆排序
- 快速排序(递归栈 ,但通常视为原地排序)
4.2 非原地排序
- 归并排序:
- 基数排序:
- 计数排序:
- 桶排序:
选择排序算法时,需要考虑以下因素:
5.1 数据规模
- 小规模数据():直接插入排序或简单选择排序,实现简单且常数因子小
- 中规模数据():希尔排序或快速排序
- 大规模数据():快速排序、归并排序或堆排序
5.2 数据初始状态
- 数据基本有序:直接插入排序(最好 )或冒泡排序(优化版 )
- 数据完全逆序:避免使用快速排序(最坏 ),选择堆排序或归并排序
- 数据随机分布:快速排序平均性能最好
- 大量重复元素:三路划分的快速排序
5.3 稳定性要求
- 需要稳定排序:归并排序(高效且稳定)、插入排序(小规模)、冒泡排序(小规模)、基数排序
- 不需要稳定排序:快速排序、堆排序(效率更高)
5.4 内存限制
- 内存有限:堆排序(原地 )、快速排序(原地)
- 内存充足:归并排序(需要 辅助空间,但稳定且高效)
5.5 关键字类型
- 整数且范围有限:计数排序或基数排序()
- 整数且位数较少:基数排序
- 浮点数或复杂对象:比较排序(快速、归并、堆)
- 字符串:基数排序(按字符)或比较排序
5.6 语言和库支持
大多数编程语言的标准库都提供了高效的排序函数:
- C:qsort(快速排序)
- C++:std::sort(快速排序+插入排序+堆排序的混合,称为Introsort)
- Java:Arrays.sort(基本类型用快速排序,对象类型用归并排序/Timsort)
- Python:sorted/list.sort(Timsort,归并排序+插入排序的混合)
- 混合排序:结合多种排序算法的优点,如Introsort(快速+堆+插入)、Timsort(归并+插入)
- 并行排序:利用多核CPU并行排序,如并行归并排序、并行快速排序
- GPU排序:利用GPU的大规模并行能力进行排序
- 外部排序优化:针对SSD等新型存储设备优化外部排序算法
- 自适应排序:根据数据特点自动选择最优排序策略
选择题
习题 1
以下排序算法中,平均时间复杂度为 且稳定的是( )
A. 快速排序 B. 堆排序 C. 归并排序 D. 希尔排序
解题思路:
本题考查排序算法的稳定性与平均时间复杂度。题干给出两个限定条件——平均时间复杂度为 且稳定——需要把四个算法逐一对照这两条要求来筛选。
详细步骤:
- 快速排序:平均 ,但不稳定
- 堆排序:平均 ,但不稳定
- 归并排序:平均 ,且稳定
- 希尔排序:平均约 ,且不稳定
- 只有归并排序同时满足“平均 ”与“稳定”这两个条件。
最终答案:
C。
习题 2
对8个元素进行排序,以下排序算法中,最坏情况下比较次数最少的是( )
A. 直接插入排序 B. 冒泡排序 C. 简单选择排序 D. 堆排序
解题思路:
本题考查四个排序算法在最坏情况下的比较次数。关键是比较时间复杂度的量级:前三个算法最坏都是 ,比较次数达到 ;而堆排序最坏只有 ,比较次数更少。
详细步骤:
- 直接插入排序:最坏比较次数
- 冒泡排序:最坏比较次数
- 简单选择排序:比较次数恒为
- 堆排序:最坏比较次数约为
- 堆排序的最坏时间复杂度为 ,比其他三个 的算法比较次数少。
最终答案:
D。
简答题
习题 3
试比较快速排序、堆排序和归并排序的优缺点,并说明各自的适用场景。
解题思路:
本题考查快速排序、堆排序与归并排序的优缺点及适用场景。答题时按“优点—缺点—适用场景”三个维度分别评述三种算法,最后按不同需求给出选择建议。
详细步骤:
- 快速排序——优点:平均时间复杂度 ,常数因子最小,实际运行效率最高;原地排序(递归栈 );缓存友好,局部性好。缺点:最坏情况 (数据已有序或基本有序,需优化基准选择);不稳定排序;递归实现有栈溢出风险。适用场景:大规模随机数据;对稳定性没有要求;内存有限;实际应用中最常用的排序算法。
- 堆排序——优点:时间复杂度恒为 ,性能稳定;原地排序,空间复杂度 ;适合实现优先队列。缺点:不稳定排序;常数因子比快速排序大;缓存不友好(跳跃式访问数组)。适用场景:对时间复杂度稳定性要求高的场景;内存有限;需要优先队列的场景(如 Top K 问题、Dijkstra 算法、任务调度)。
- 归并排序——优点:时间复杂度恒为 ,性能稳定;稳定排序;适合链表排序(不需要额外数组空间);适合外部排序。缺点:空间复杂度 ,需要额外辅助数组;常数因子比快速排序大;不是原地排序(标准实现)。适用场景:对稳定性有要求的场景;链表排序;外部排序(数据量大,内存不足);数据量较大且需要稳定性能的场景。
- 选择建议——追求最高平均性能、不要求稳定时选快速排序;要求性能稳定、内存有限且不要求稳定时选堆排序;要求稳定,或链表排序,或外部排序时选归并排序。实际应用中,大多数语言的标准库使用混合排序算法(如 Introsort、Timsort),结合了多种排序算法的优点。
最终答案:
快速排序平均性能最好但最坏可达 且不稳定;堆排序时间复杂度恒为 、空间 但不稳定且缓存不友好;归并排序稳定、时间恒为 但需 辅助空间,适合链表与外部排序。
