排序算法系列 01：排序这事儿，没你想的那么简单
学算法，排序基本上是第一个绕不过去的坎。
表面上看，排序就是把一堆数据按规则摆整齐：
原始数据：5, 2, 9, 1, 7
升序排列：1, 2, 5, 7, 9
降序排列：9, 7, 5, 2, 1
就这？对，就这。但往下挖你会发现，光是"怎么摆整齐"这件事，前人就琢磨出了十几种完全不同的思路——交换、选择、插入、分治、堆、桶、计数……每一种背后都是一套算法设计哲学。
所以我一直觉得，排序算法是理解"算法到底在干嘛"的最佳入口。
排序算法到底在解决什么问题？
一句话：把一组数据按指定规则重新排列。
这个"规则"可以是：
- 数字从小到大（升序）
- 数字从大到小（降序）
- 字符串按字典序
- 对象按某个字段排，比如按年龄、价格、时间
举个例子，有这么一组用户数据：
[
{ "name": "Tom", "age": 20 },
{ "name": "Jack", "age": 18 },
{ "name": "Lucy", "age": 22 }
]
按 age 升序排完就是：
[
{ "name": "Jack", "age": 18 },
{ "name": "Tom", "age": 20 },
{ "name": "Lucy", "age": 22 }
]
核心问题就是：怎么又快又好地把无序变有序。
为什么值得花时间学？
说实话，日常开发你直接调 .sort() 就完事了。但排序算法值得学，原因有三个：
第一，排序无处不在。 电商的价格排序、搜索的相关度排序、排行榜的分数排序、日志的时间排序——底层都是排序。你不一定要自己写排序，但你得知道它是怎么工作的。
第二，它是理解复杂度最直观的教材。 同样是排序，冒泡要跑 O(n²)，快排只要 O(n log n)，数据量一大差距是数量级的。通过排序，你能真切感受到"复杂度不是纸上的数学，是实打实的性能差距"。
第三，它包含了大量经典算法思想。 你后面学动态规划、学图算法、学各种高级数据结构，很多核心思想其实在排序里就见过了：
- 冒泡排序 → 相邻交换
- 选择排序 → 找最值
- 插入排序 → 维护局部有序
- 归并排序 → 分治
- 快速排序 → 分治 + 划分
- 堆排序 → 堆结构
- 计数排序 → 空间换时间
- 桶排序 → 分布映射
- 基数排序 → 逐位处理
这些思想反复出现，学一次受用很久。
排序算法有哪些？
大的分两类：比较类和非比较类。
比较类排序
靠比较两个元素谁大谁小来决定顺序，是最常见的一类。
| 算法 | 平均时间复杂度 | 空间复杂度 | 稳定性 |
|---|---|---|---|
| 冒泡排序 | O(n²) | O(1) | 稳定 |
| 选择排序 | O(n²) | O(1) | 不稳定 |
| 插入排序 | O(n²) | O(1) | 稳定 |
| 希尔排序 | 取决于步长序列 | O(1) | 不稳定 |
| 归并排序 | O(n log n) | O(n) | 稳定 |
| 快速排序 | O(n log n) | O(log n) | 不稳定 |
| 堆排序 | O(n log n) | O(1) | 不稳定 |
非比较类排序
不比大小，而是利用数据本身的特征（范围、位数、分布）来排。
| 算法 | 平均时间复杂度 | 空间复杂度 | 稳定性 |
|---|---|---|---|
| 计数排序 | O(n + k) | O(k) | 稳定 |
| 桶排序 | O(n + k) | O(n + k) | 稳定 |
| 基数排序 | O(n × k) | O(n + k) | 稳定 |
这里 n 是数据量，k 是数据范围/桶数/位数。
非比较类排序在特定条件下非常快，但有前提限制。比如计数排序，数据范围太大就不适用了。
评价排序算法看什么？
三个核心指标。
时间复杂度
就是"数据量翻倍，算法要多跑多久"。
常见的几档：
O(n) < O(n log n) < O(n²)
数据量小的时候差距不明显，数据量一上去，O(n²) 和 O(n log n) 就是天壤之别。1 万条数据，O(n²) 要比较 1 亿次，O(n log n) 大概 13 万次。
空间复杂度
排序过程中需要多少额外内存。
冒泡、选择、插入这些基本上是原地排序，不需要额外空间。归并排序需要一个同等大小的临时数组，计数排序需要一个计数数组。
稳定性
如果两个元素值相等，排完序后它们的先后顺序还能不能保持不变——能保持就叫"稳定"。
举个例子：
原始：A(90), B(80), C(90)
按分数升序：B(80), A(90), C(90)
如果排完后 A 还在 C 前面，说明排序是稳定的。
稳定性什么时候有用？多字段排序的时候。比如先按名字排，再按成绩排，如果第二次排序是稳定的，成绩相同的人还能保持之前按名字排好的顺序。
各种排序算法一句话概括
后面的系列文章会逐个展开，这里先简单过一遍：
冒泡排序——反复比较相邻元素，大的往后挪，每轮把最大的"冒"到末尾。最直观，但也最慢。
选择排序——每轮从剩余元素里挑最小的，放到当前位置。思路简单，交换次数少，但比较次数省不了。
插入排序——像打扑克牌一样，拿到新牌插到手牌的合适位置。数据量小或者基本有序时表现不错。
希尔排序——插入排序的加强版。先按较大间隔分组排序，逐步缩小间隔，最终完成排序。
归并排序——先拆后合。把数组不断对半拆，拆到单个元素，再两两合并成有序数组。性能稳定，永远是 O(n log n)。
快速排序——选个基准值，比它小的扔左边，比它大的扔右边，递归处理。平均性能最好，实际开发中用得最多。
堆排序——先把数组建成堆，然后不断取堆顶。时间复杂度稳定，空间占用小，但实际跑起来常数因子比快排大。
计数排序——统计每个值出现几次，直接按计数输出。快，但只适合整数且范围不大的场景。
桶排序——把数据分到多个桶里，桶内各自排序，最后拼起来。数据分布均匀时效果很好。
基数排序——从最低位到最高位，逐位排序。适合整数或等长字符串。
实际该用哪个？
没有万能的排序算法，选型看场景：
| 场景 | 推荐 |
|---|---|
| 数据量很小（几十个） | 插入排序，简单够用 |
| 数据基本有序 | 插入排序，接近 O(n) |
| 通用场景追求性能 | 快速排序 |
| 要求排序稳定 | 归并排序 |
| 内存吃紧 | 堆排序 |
| 整数且范围不大 | 计数排序 |
| 数据均匀分布 | 桶排序 |
| 多位整数/定长字符串 | 基数排序 |
实际工程里，大多数语言标准库的排序实现都是混合策略——比如 V8 的 Array.sort 用的是 TimSort（归并 + 插入的混合体），小数组切插入排序，大数组走归并。
这个系列接下来怎么写
后面会按这个顺序逐个拆解：
- 排序算法总览（就是本篇）
- 冒泡排序
- 选择排序
- 插入排序
- 希尔排序
- 归并排序
- 快速排序
- 堆排序
- 计数排序
- 桶排序
- 基数排序
- 排序算法对比与实战选型
每篇会覆盖：算法思想、执行过程图解、代码实现、复杂度分析、稳定性、优缺点、适用场景。
写在最后
排序这件事，目标很朴素——无序变有序。
但不同算法解决它的方式完全不同：有的靠交换，有的靠选择，有的靠分治，有的借助特殊数据结构，有的干脆绕开比较直接计数。
学排序，不是为了手写排序（面试除外），而是通过它理解算法设计的不同流派。这些思想搞明白了，后面遇到更复杂的问题，你会发现很多套路似曾相识。
下一篇，从最简单的冒泡排序开始。
系列导航