如果在待排序序列中存在多个关键字相同的元素，经过排序后这些元素的相对次序保持不变，则称该排序算法是稳定的；否则是不稳定的。
例：排序前 3a, 1, 3b, 2（3a、3b 关键字相同）。
1, 2, 3a, 3b（3a 仍在 3b 前）1, 2, 3b, 3a（相对顺序改变）| 排序算法 | 稳定性 | 平均时间 | 空间 |
|---|---|---|---|
| 直接插入排序 | ✅ 稳定 | $O(n^2)$ | $O(1)$ |
| 折半插入排序 | ✅ 稳定 | $O(n^2)$ | $O(1)$ |
| 希尔排序 | ❌ 不稳定 | $O(n^{1.3})$ | $O(1)$ |
| 冒泡排序 | ✅ 稳定 | $O(n^2)$ | $O(1)$ |
| 快速排序 | ❌ 不稳定 | $O(n\log n)$ | $O(\log n)$ |
| 简单选择排序 | ❌ 不稳定 | $O(n^2)$ | $O(1)$ |
| 堆排序 | ❌ 不稳定 | $O(n\log n)$ | $O(1)$ |
| 归并排序 | ✅ 稳定 | $O(n\log n)$ | $O(n)$ |
| 基数排序 | ✅ 稳定 | $O(d(n+r))$ | $O(n+r)$ |
| 计数排序 | ✅ 稳定 | $O(n+k)$ | $O(k)$ |
| 桶排序 | ✅ 稳定 | $O(n)$ | $O(n)$ |
[3a,1,3b,2]。[3a,3b,1,2] 选 3a 为基准。[3a,1,3b,2] 第 2 趟交换后 3a、3b 反了。[4a,4b,3]。< 前面元素才移动，相等不交换。对 [5a, 3, 5b, 1, 2] 用直接插入排序：
[5a, 3, 5b, 1, 2]
[3, 5a, 5b, 1, 2] 插入 3
[3, 5a, 5b, 1, 2] 插入 5b（=5a，不移动，插在 5a 后）✓稳定
[1, 3, 5a, 5b, 2] 插入 1
[1, 2, 3, 5a, 5b] 插入 2结果 5a 仍在 5b 前，稳定 ✓。快速排序选第一个为基准时，5a、5b 可能反序，不稳定 ✗。
（暂无关联知识点）