袋鼠知识库

主题

十大经典排序算法对比 ​

1. 为什么需要一页“横向比较” ​

前面的排序主章和图解页更强调“把单个算法讲透”。但真正到做题、面试、工程选型时，难点往往不是“某个算法会不会写”，而是：

  1. 为什么这里该选归并，不该选快排。
  2. 为什么这里宁可用计数排序，也不做比较排序。
  3. 为什么数据近乎有序时，插入排序反而不差。
  4. 为什么系统库里经常混合使用多种排序策略。

所以这一页专门解决“横向比较”的问题。

2. 十大经典排序算法总表 ​

算法平均复杂度最坏复杂度空间复杂度稳定性原地核心思想
冒泡排序O(n^2)O(n^2)O(1)稳定是相邻交换，大数后沉
选择排序O(n^2)O(n^2)O(1)不稳定是每轮选最小值
插入排序O(n^2)O(n^2)O(1)稳定是把当前元素插入已排序区
希尔排序视步长而定O(n^2)O(1)不稳定是分组插入，逐步缩小间隔
归并排序O(n log n)O(n log n)O(n)稳定否分治拆分，有序合并
快速排序O(n log n)O(n^2)递归栈不稳定近似原地基准划分
堆排序O(n log n)O(n log n)O(1)不稳定是维护堆顶最值
计数排序O(n+k)O(n+k)O(k)稳定否统计频次直接定位
桶排序平均 O(n+k)取决于桶内排序取决于桶数视实现而定否按范围分桶
基数排序O(d(n+r))O(d(n+r))O(n+r)稳定否按位分配，多轮稳定排序

说明：

  1. k 常表示值域大小或桶数。
  2. d 表示位数。
  3. r 表示基数，如十进制排序时的 10。

3. 三类最基础的 O(n^2) 算法 ​

3.1 冒泡排序 ​

优点：

  1. 过程直观。
  2. 稳定。
  3. 已经有序时可通过提前退出优化。

缺点：

  1. 交换次数多。
  2. 数据量稍大时性能迅速变差。

适用：

  1. 教学演示。
  2. 极小规模数据。
  3. 想强调“局部交换累积成全局有序”的过程时。

3.2 选择排序 ​

优点：

  1. 思路很干净。
  2. 交换次数通常少于冒泡。

缺点：

  1. 不稳定。
  2. 时间复杂度没有本质优势。

适用：

  1. 讲清“每轮确定一个最终位置”的思想。
  2. 小规模教学示例。

3.3 插入排序 ​

优点：

  1. 稳定。
  2. 对近乎有序的数据非常友好。
  3. 小规模排序时常常很有竞争力。

缺点：

  1. 大规模无序数据下仍然是 O(n^2)。

适用：

  1. 数据几乎有序。
  2. 在线插入维护局部顺序。
  3. 大型混合排序里作为小区间收尾算法。

4. 希尔排序：为什么它常被叫作“改良版插入排序” ​

希尔排序的核心思想是：
先让相距较远的元素进行比较和插入，使整体更快接近有序；然后逐步缩小间隔，直到最后变成普通插入排序。

go
func ShellSort(nums []int) {
    for gap := len(nums) / 2; gap > 0; gap /= 2 {
        for i := gap; i < len(nums); i++ {
            temp := nums[i]
            j := i
            for j >= gap && nums[j-gap] > temp {
                nums[j] = nums[j-gap]
                j -= gap
            }
            nums[j] = temp
        }
    }
}

它的复杂度强烈依赖步长序列，所以教材里常见“平均复杂度不固定”的说法。要抓住的重点是：它并不是魔法，而是在“先粗调，再细调”。

5. 三类最核心的 O(n log n) 比较排序 ​

5.1 归并排序 ​

优势：

  1. 稳定。
  2. 最坏复杂度稳定在 O(n log n)。
  3. 非常适合链表排序、外部排序和并行拆分。

代价：

  1. 额外空间通常为 O(n)。

适用：

  1. 需要稳定性。
  2. 数据量较大。
  3. 可接受额外内存。

5.2 快速排序 ​

优势：

  1. 平均性能极强。
  2. 缓存局部性通常较好。
  3. 工程里常常非常快。

代价：

  1. 最坏可能退化到 O(n^2)。
  2. 不稳定。

适用：

  1. 一般内存排序。
  2. 追求平均速度。
  3. 可配合随机化或三数取中优化。

5.3 堆排序 ​

优势：

  1. 最坏复杂度稳定在 O(n log n)。
  2. 原地排序。

代价：

  1. 不稳定。
  2. 常数和缓存表现常不如快排。

适用：

  1. 需要原地且有稳定上界。
  2. 更关注理论最坏复杂度。

6. 非比较排序：什么时候可以快过 O(n log n) ​

很多人以为排序下界永远是 O(n log n)。这是不完整的。
O(n log n) 下界针对的是比较排序。如果你能利用数值范围、位数结构或分布信息，就可以跳出比较模型。

6.1 计数排序 ​

适用前提：

  1. 元素是整数。
  2. 值域不大。

核心思想：

  1. 统计每个值出现次数。
  2. 再按次数回写。
go
func CountingSort(nums []int, maxVal int) []int {
    count := make([]int, maxVal+1)
    for _, x := range nums {
        count[x]++
    }
    out := make([]int, 0, len(nums))
    for v, c := range count {
        for ; c > 0; c-- {
            out = append(out, v)
        }
    }
    return out
}

优势：

  1. 线性时间。
  2. 可做稳定版本。

限制：

  1. 值域太大时空间爆炸。

6.2 桶排序 ​

适用前提：

  1. 数据分布相对均匀。
  2. 能按范围自然分桶。

核心思想：

  1. 先把元素分散到多个桶。
  2. 各桶内部再排。
  3. 按桶顺序拼回。

桶排序真正好用的前提不是“名字高级”，而是你对数据分布有把握。

6.3 基数排序 ​

适用前提：

  1. 键可以分解为多个位。
  2. 每一位都能稳定地分配排序。

经典场景：

  1. 固定位数整数。
  2. 字符串字典序的某些变形。

基数排序最关键的概念不是“按位排”，而是：
每一轮子排序必须稳定，否则前一轮建立的低位顺序会被破坏。

7. 做题和工程里的选型建议 ​

7.1 如果题目说“数组基本有序” ​

优先想到：

  1. 插入排序。
  2. 在更复杂问题里，也要考虑“局部插入代价很小”的特性。

7.2 如果题目强调“稳定排序” ​

优先想到：

  1. 插入排序。
  2. 归并排序。
  3. 计数排序 / 基数排序的稳定实现。

7.3 如果题目强调“值域很小” ​

优先想到：

  1. 计数排序。
  2. 桶排序。
  3. 基数排序。

不要机械地上快排。

7.4 如果题目强调“最坏也不能太慢” ​

优先想到：

  1. 归并排序。
  2. 堆排序。

7.5 如果题目强调“内存很紧” ​

优先想到：

  1. 堆排序。
  2. 快速排序的原地版本。
  3. 插入排序用于小规模。

8. 工业实现为什么常用混合排序 ​

现实语言标准库很少完全只靠某一种排序。常见做法是混合：

  1. 大区间用快速排序。
  2. 小区间切换到插入排序。
  3. 递归深度过深时切换到堆排序。

这就是著名的 introsort 思路。

原因很务实：

  1. 快排平均快。
  2. 插入排序收尾小区间很高效。
  3. 堆排序能兜住最坏情况。

这也说明成熟工程实现关注的是整体表现，而不是迷信单一算法。

9. 最常见的误区 ​

  1. 把快排当成所有场景下的默认最优。
  2. 认为 O(n log n) 一定比 O(n^2) 实际更快。
  3. 忽视稳定性要求。
  4. 不区分比较排序和非比较排序。
  5. 只背表，不知道每个算法真正擅长的输入条件。

10. 一张“怎么选”的速查表 ​

场景优先考虑
小规模、近乎有序插入排序
要稳定，且规模较大归并排序
平均性能优先快速排序
要原地且要最坏上界堆排序
值域小、整数计数排序
分布均匀、可分桶桶排序
多位整数或定长键基数排序

11. 学完这一页后应达到的标准 ​

你不应只会回答“哪个复杂度最低”，而应能回答：

  1. 它为什么稳定或不稳定。
  2. 它为什么需要或不需要额外空间。
  3. 它是比较排序还是非比较排序。
  4. 它在哪类输入上会特别好，在哪类输入上会明显吃亏。

这才是真正能把排序算法用起来的状态。