std_list的排序算法源码
list::sort采用非递归归并排序,利用链表特性高效合并,避免递归和多次移动,适合链表结构。
std_list的排序算法源码
std_list 的排序算法源码
源码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
void sort() {
// 如果链表为空,或者只有一个元素,则不需要排序,直接返回
if (node->next == node || link_type(node->next)->next == node)
return;
list carry; // 一个临时链表,用于暂存当前切下来的单个节点
list counter[64]; // 模拟归并排序的“桶”,最多支持 2^64 个元素(非常大)
int fill = 0; // 当前 counter 中被占用的最大桶编号 + 1(即桶的“位数”)
// 主循环:依次从原链表中切出元素,并进行“二进制合并”
while (!empty()) {
// 1. 把 this 的第一个元素(begin())剪下来放入 carry(cut/splice)
// carry 现在只包含一个元素,相当于一个 size 为 1 的有序子链表
carry.splice(carry.begin(), *this, begin());
int i = 0;
// 2. 查找 counter[i] 是否为空,如果不为空,则执行合并操作
// 直到找到一个空桶为止。这个过程类似二进制加法中的“进位合并”。
while (i < fill && !counter[i].empty()) {
// merge 是就地归并排序(两个有序链表合并)
counter[i].merge(carry); // merge 到 counter[i]
carry.swap(counter[i++]); // 交换 carry 和 counter[i]:carry 保存合并结果,counter[i] 清空
}
// 3. 找到空桶(或开辟新桶)后,把合并好的 carry 放入其中
carry.swap(counter[i]);
// 4. 如果当前使用到了新桶(超过原先 fill),就更新 fill
if (i == fill) ++fill;
}
// 所有元素已经切分并归并到 counter[] 中,现在将这些桶中的结果最终合并
// counter[i] 表示 2^i 大小的有序链表,将它们两两归并成一个最终结果
for (int i = 1; i < fill; ++i)
counter[i].merge(counter[i - 1]); // 每次把更小的桶归并进更大的桶
// 将最终合并好的结果(在 counter[fill - 1])与 this 交换
// 完成排序:this 持有有序链表
swap(counter[fill - 1]);
}
利用 归并排序思想,对链表进行排序。
通过
counter
数组模拟二进制加法的“桶”:每次拿一个元素(一个单节点链表)归并到对应桶。
遇到满桶就合并,类似二进制进位。
每个桶的含义
counter[0]
:可以放 2⁰ = 1 个元素的有序链表counter[1]
:可以放 2¹ = 2 个元素的有序链表counter[2]
:可以放 2² = 4 个元素的有序链表 …counter[i]
:存储一个大小为 2ⁱ 的有序链表段
这个结构类似于二进制加法中每一位的进位机制。
使用
splice
和merge
完成链表间的元素移动和有序合并。时间复杂度稳定为 O(n log n),且不额外分配内存。
这个算法的精妙之处在于:
- 每次切一个元素,用
carry
装起来; - 使用
counter[]
模拟“二进制加法”归并,效率为 O(N log N); - 无需递归,且链表操作都是 splice/merge,无需额外空间分配,效率高。
为什么不是用常见排序(快排、堆排、插排)?
快速排序(QuickSort)
- 快排依赖 随机访问(下标访问) 来做分区(pivot)。
- 但链表是线性结构,没有 O(1) 的
arr[i]
,只有顺序访问,导致快排在链表上效率 极低。 - 快排的“分割”过程在链表上实现起来也很麻烦。
插入排序(Insertion Sort)
- 插入排序虽然链表上可行(因为插入代价低),但整体复杂度是 O(n²),性能太差。
- STL 对性能要求极高,无法接受这种算法。
堆排序(HeapSort)
- 堆需要随机访问(数组结构),链表无法高效构建堆结构。
为什么选择这种“二进制归并排序”?
归并排序最适合链表
归并排序的关键优势:
- 无需随机访问,纯靠指针操作。
- 可以原地进行链表合并:merge 操作对链表来说代价非常低(O(n) 且稳定)。
- STL 的
list::merge()
本身就是高效稳定的链表归并。
这段代码实现的是“自底向上的归并排序”
- 与递归版归并排序(自顶向下)不同,这种做法是非递归的,用数组
counter[64]
来管理每一个归并层。 - 优点是不需要递归、不消耗栈空间,适合 STL 要求的高性能、低资源消耗。
时间复杂度
- 整体复杂度是 O(n log n),在链表上这是能达到的最佳排序复杂度。
- 并且这个排序是 稳定的,对于结构体或复杂对象尤为重要。
模拟例子
假设有一串链表元素:
7 -> 3 -> 9 -> 1 -> 5
算法步骤:
- 每次切下一个节点形成
carry
(类似 [7], [3], …)。 - 尝试和已有桶归并,如果
counter[0]
有元素,那就合并形成一个[3,7]
的桶进入counter[1]
。 - 像二进制加法的进位一样,不断向高位合并,最多 log₂(n) 次。
这个过程模拟了如下操作:
输入 | carry | counter[0] | counter[1] | counter[2] |
---|---|---|---|---|
7 | [7] | |||
3 | [3] | [7] | ||
合并 | [3,7] | |||
9 | [9] | [3,7] | ||
1 | [1] | [9] | [3,7] | |
合并 | [1,9] | |||
合并 | [1,3,7,9] |
- 没有额外分配内存(不像递归归并那样需要开临时数组)
- 稳定排序(关键字相同的元素顺序不变)
- 异常安全(STL 容器设计时非常重视)
总结
方案 | 是否适合链表 | 是否稳定 | 时间复杂度 | STL 是否采用 |
---|---|---|---|---|
快排 | ❌ 依赖随机访问 | 不稳定 | O(n log n) 平均 | ❌ |
插排 | ✅ 结构简单 | 稳定 | ❌ O(n²) 最坏 | ❌ |
递归归并 | ✅ | 稳定 | ✅ O(n log n) | ✅ 但递归会栈爆 |
自底向上归并 | ✅ 最优选择 | ✅ 稳定 | ✅ O(n log n) | ✅✔ |
STL list::sort()
的实现就是采用了自底向上的归并排序算法,确保链表排序的最优性能和稳定性。
本文由作者按照 CC BY 4.0 进行授权