比较类排序算法 #

这类算法依赖元素间的比较操作，是日常开发中最常用的排序类别。

冒泡排序 #

• 优劣：实现门槛极低，几行代码就能搞定，不需要额外内存，但最坏时间复杂度为O(n²)，数据量稍大就慢到无法实用，属于稳定排序（相同元素不会交换位置）。
• 适用场景：基本没有生产场景会用，仅用于教学演示排序的基本逻辑。

插入排序 #

• 优劣：无额外内存开销，对接近有序的小规模数据效率极高（最好时间复杂度O(n)），但数据完全无序时性能暴跌至O(n²)，属于稳定排序。
• 适用场景：常作为快速排序、归并排序等复杂算法的底层子过程（比如递归到小规模数据时切换插入排序），或处理本身接近有序的小数据集。

选择排序 #

• 优劣：空间开销O(1)，但无论数据是否有序，时间复杂度始终为O(n²)，且属于不稳定排序（相同元素可能被交换位置），性能略优于冒泡但依然低效。
• 适用场景：仅当内存极端紧张，且数据规模极小的时候才会考虑。

快速排序 #

• 优劣：平均时间复杂度O(nlogn)，空间开销主要来自递归栈（O(logn)），实际运行速度在比较类排序中基本最快，但遇到完全有序的数据时会退化为O(n²)（现在通常有随机选基准值的优化），属于不稳定排序。
• 适用场景：绝大多数通用场景，尤其是数据规模大、分布随机的情况，工业界广泛使用（比如Python的list.sort()、Java的Arrays.sort()底层都是优化过的快排）。

归并排序 #

• 优劣：时间复杂度稳定在O(nlogn)，不受数据分布影响，属于稳定排序，但需要额外O(n)内存存储中间结果，实际运行速度略慢于快排。
• 适用场景：要求稳定排序且数据规模较大的场景，或外部排序（数据过大无法全部加载到内存时）。

堆排序 #

• 优劣：时间复杂度O(nlogn)，空间开销O(1)，但缓存友好性差（堆的元素访问是跳跃式的，无法利用CPU缓存），实际运行速度比快排慢，属于不稳定排序。
• 适用场景：内存有限且不需要稳定排序的大规模数据排序，或需要动态维护有序集合的场景（比如实现优先队列）。

非比较类排序算法 #

这类算法不依赖元素比较，利用数据特性实现排序，性能通常更优但适用范围有限。

计数排序 #

• 优劣：时间复杂度O(n+k)（k是数据取值范围），空间开销O(k)，属于稳定排序，但仅能处理整数，且k不能过大（否则内存占用过高）。
• 适用场景：数据为整数、取值范围明确且不大的情况，比如学生0-100分的成绩排序、员工年龄排序。

桶排序 #

• 优劣：平均时间复杂度O(n)，空间开销O(n+k)（k是桶的数量），属于稳定排序，但依赖数据均匀分布，若数据扎堆，某个桶内元素过多会退化为插入排序或快排。
• 适用场景：数据分布均匀的大规模数据集，比如电商平台的订单金额排序（假设金额集中在合理区间）。

基数排序 #

• 优劣：时间复杂度O(d*(n+k))（d是数据位数，k是基数，比如十进制k为10），空间开销O(n+k)，属于稳定排序，仅能处理可按位拆分的数据（比如整数、字符串）。
• 适用场景：整数、字符串这类可按位处理的大规模数据，比如手机号排序、身份证号排序。

快速选择指南 #

• 通用首选：快速排序（大规模随机数据，无稳定要求）
• 稳定排序需求：归并排序（通用场景）、计数/桶/基数排序（需匹配数据类型）
• 小规模接近有序数据：插入排序
• 内存极度紧张：堆排序（大规模）、选择排序（仅极小数据）
• 非整数/取值范围极大的离散数据：直接使用快排或归并排序

内容的提问来源于stack exchange，提问作者Lucas Li