常见排序算法详解与分类
在数据结构的学习中，排序算法是最基础且核心的部分之一。常见的排序算法包括冒泡、插入、选择、希尔、堆、归并、快速、桶、计数及基数排序等。
以下是常用排序算法的时间与空间复杂度对比：
排序算法的分类
这么多排序算法，我们可以从不同维度进行划分，这有助于理解它们的特性：
1. 数据规模
- 内部排序：待排序数据能全部加载进内存。
- 外部排序：数据量过大，无法一次性放入内存，需借助外部存储交换数据。
2. 稳定性
- 稳定排序：冒泡、插入、归并。
- 不稳定排序：快速、选择、希尔、堆。
3. 时间复杂度
- O(N)：桶排序、计数排序、基数排序。
- O(NlogN)：快速、希尔、归并、堆排序。
- O(N²)：冒泡、插入、选择排序。
4. 算法思想
- 分治：快速、归并。
- 插入：希尔、插入。
- 选择：堆、选择。
- 交换：冒泡、快速。
需要注意的是，上述分类并非绝对界限，更多是基于算法特性的总结。理解各类算法的特点后，自然能掌握其适用场景。
如何评估排序算法
评估一个排序算法的质量，通常关注以下几个维度：
时间复杂度
这是衡量算法性能最关键的指标。排序的核心操作是'比较'和'移动'元素，优化目标即减少这两类操作的次数。由于输入数据的分布不同，同一算法在不同情况下的表现差异很大，因此需要分析最好、最坏及平均时间复杂度，以全面了解算法特性。
空间复杂度
指执行算法所需的辅助存储空间（不含原数据占用）。若空间复杂度为 O(1)，说明仅需常量级辅助空间，效率较高。大多数简单排序如冒泡、插入、选择的空间复杂度均为 O(1)。
稳定性
稳定性在实际应用中非常重要。通俗来说，若待排序数组中存在相等元素，排序后它们的相对位置保持不变。例如，原数组中有两个值为 6 的元素，排序后它们的前后顺序不应互换。在实际业务中，如按年龄排序学生名单，若两人年龄相同，保持原有入学顺序往往更为合理。
算法实现复杂度
除了时间和空间开销，算法本身的逻辑设计复杂度也会影响开发和维护成本。像冒泡、插入、选择这类属于简单排序，逻辑直观；而归并、堆排序等则涉及更复杂的递归或树结构管理。
