排序算法的分类法

排序算法可以按照多个维度进行分类，包括 自适应性、原地性、稳定性、比较性 等。以下是详细的分类说明，并涵盖 选择排序、冒泡排序、插入排序、快速排序、归并排序、堆排序、桶排序、计数排序、基数排序、希尔排序。

1. 按自适应性（Adaptivity）划分

定义：算法的时间复杂度是否受输入数据的有序程度影响。

算法 是否自适应 说明
选择排序 ❌ 无论数据是否有序，时间复杂度始终为 O(n²)
冒泡排序 ✅ 优化版本可在数据有序时提前终止（最好情况 O(n)）
插入排序 ✅ 对近乎有序数据效率高（最好情况 O(n)）
快速排序 ❌（通常） 标准实现不关心初始顺序，但某些优化版本可能自适应
归并排序 ❌ 无论数据是否有序，时间复杂度始终为 O(n log n)
堆排序 ❌ 时间复杂度固定为 O(n log n)
桶排序 ✅ 数据分布均匀时效率高（接近 O(n)）
计数排序 ❌ 时间复杂度固定为 O(n + k)
基数排序 ❌ 时间复杂度固定为 O(nk)
希尔排序

2. 按原地性（In-Place）划分

定义：算法是否需要额外的存储空间（O(1) 额外空间为原地排序）。注意并非一点空间都不行，这样交换都做不到了！

算法 是否原地排序 空间复杂度
选择排序 ✅ O(1)
冒泡排序 ✅ O(1)
插入排序 ✅ O(1)
快速排序 ✅（递归栈除外） O(log n)（递归栈）
归并排序 ❌ O(n)
堆排序 ✅ O(1)
桶排序 ❌ O(n + k)
计数排序 ❌ O(n + k)
基数排序 ❌ O(n + k)

3. 按稳定性（Stability）划分

定义：算法是否能保持相等元素的原始相对顺序。

算法 是否稳定 说明
选择排序 ❌ 交换操作可能改变相等元素的顺序
冒泡排序 ✅ 相邻交换，相等元素不会交换
插入排序 ✅ 插入操作不影响相等元素的顺序
快速排序 ❌（标准实现） 分区操作可能改变相等元素的顺序
归并排序 ✅ 归并时保持相等元素的顺序
堆排序 ❌ 堆调整可能破坏相等元素的顺序
桶排序 ✅（取决于子排序算法） 通常使用稳定排序（如插入排序）
计数排序 ✅ 统计计数时保持顺序
基数排序 ✅（LSD实现） 依赖稳定的子排序（如计数排序）

4. 按比较性（Comparison-Based）划分

定义：算法是否通过比较元素来决定顺序。

算法 是否比较排序 说明
选择排序 ✅ 每次选择最小/最大元素
冒泡排序 ✅ 相邻元素比较交换
插入排序 ✅ 逐个比较插入正确位置
快速排序 ✅ 基于比较的分区
归并排序 ✅ 比较后归并
堆排序 ✅ 基于堆的比较
桶排序 ❌ 数据分桶，不直接比较
计数排序 ❌ 统计频率，不比较
基数排序 ❌ 按位分配，不直接比较

5. 综合分类表

算法 自适应性 原地性 稳定性 比较性 时间复杂度（平均） 适用场景
选择排序 ❌ ✅ ❌ ✅ O(n²) 小数据量、简单实现
冒泡排序 ✅ ✅ ✅ ✅ O(n²) 教学、小数据量
插入排序 ✅ ✅ ✅ ✅ O(n²) 近乎有序数据、小数据量
快速排序 ❌ ✅ ❌ ✅ O(n log n) 通用排序、内存高效
归并排序 ❌ ❌ ✅ ✅ O(n log n) 大数据、稳定排序
堆排序 ❌ ✅ ❌ ✅ O(n log n) 内存受限、不需要稳定
桶排序 ✅ ❌ ✅ ❌ O(n + k) 数据分布均匀
计数排序 ❌ ❌ ✅ ❌ O(n + k) 小范围整数
基数排序 ❌ ❌ ✅ ❌ O(nk) 整数/字符串排序

6. 总结

  • 自适应性：插入排序、冒泡排序对近乎有序数据更高效。
  • 原地性：选择排序、冒泡排序、插入排序、快速排序、堆排序适合内存受限场景。
  • 稳定性：归并排序、计数排序、基数排序适合需要保持顺序的场景。
  • 比较性：非比较排序（计数、基数、桶排序）在特定数据上比比较排序更快。

选择建议：

  • 通用排序 → 快速排序（平均 O(n log n)）。
  • 稳定排序 → 归并排序、计数排序、基数排序。
  • 小数据量 → 插入排序、冒泡排序。
  • 大数据量 → 归并排序（外部排序）、基数排序（整数排序）。

20，25，30，15，10，6，40，8
20.25.15.10.6.30.8.40
20.15.10.6.25.8.30.40
15.10.6.20.8.25.30.40