文章

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ⁱ 的有序链表段

      这个结构类似于二进制加法中每一位的进位机制。

  • 使用 splicemerge 完成链表间的元素移动和有序合并。

  • 时间复杂度稳定为 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

算法步骤:

  1. 每次切下一个节点形成 carry(类似 [7], [3], …)。
  2. 尝试和已有桶归并,如果 counter[0] 有元素,那就合并形成一个 [3,7] 的桶进入 counter[1]
  3. 二进制加法的进位一样,不断向高位合并,最多 log₂(n) 次。

这个过程模拟了如下操作:

输入carrycounter[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 进行授权