链表排序

  在学习STL中的双向链表std::list时，被它的sort()函数惊艳到，发现《STL源码剖析》一书中对该函数草草带过，遂分析一波。

std::list::sort()

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

void sort()
{
  if (node->next == node || node->next->next == node) return;
  list carry;
  list bucket[64];
  int fill = 0;
  while (!empty()) {
    carry.splice(carry.begin(), *this, begin());
    int i = 0;
    while (i < fill && !bucket[i].empty()) {
      carry.merge(bucket[i]);
      ++i;
    }
    bucket[i].swap(carry);
    if (i == fill)  ++fill;
  }
  for (int i = 1; i < fill; ++i) {
    bucket[i].merge(bucket[i - 1]);
  }
  swap(bucket[fill - 1]);
}

  这段代码用到了 3 个std::list的成员函数：

  • void splice(const_iterator pos, list& other, const_iterator it);
    从other转移it所指向的元素到*this，元素被插入到pos所指向的元素之前。
    时间复杂度O(1)。

  • void merge(list& other);
    归并两个升序排序链表为一个，不复制元素，操作后链表other变为空。
    若链表*this长度为 m，链表other长度为 n，则至多进行m + n - 1次比较。

  • void swap(list& other);
    与链表other交换内容。
    时间复杂度O(1)。

算法思想

  • 首先判断链表是否为空或只有一个元素，若是，直接返回。

  • 准备 3 个变量：

    • list carry：每次从原链表中搬运一个头节点出来。
    • list bucket[64]：64 个桶，桶的容量是2^桶号，元素入桶时均有序。
    • int fill：当前所用桶的数目。

  • while 循环：

    1. 第 8 行：carry取数。
      从原链表取一个元素，若无元素可取，跳转到 for 循环。
    2. 第 9 - 14 行：将所取数入桶bucket。
      i从0到fill - 1循环
      若bucket[i]非空，则将其归并到carry；
      若bucket[i]为空，将carry中的元素放入bucket[i]，并跳出循环。
    3. 第 15 行：维护fill。 若步骤 2 中i执行到i == fill才跳出循环，即表示bucket[fill]有元素（满了），则执行++fill，增加一个桶数。

  • for 循环：
    将bucket[0]到bucket[fill - 2]的每个桶归并到bucket[fill - 1]。

图解

  例如对链表3 → 7 → 4 → 1 → 9 → 8 → 5 → 2 → 6进行排序。

总结

  从图中可以形象地看出，这是利用了二进制的进位思想，实现了非递归的归并排序。《STL源码剖析》中并未分析该算法，说它是 quick sort，想必是写错了。

  时间复杂度O(nlogn)，空间复杂度O(1)（由于是链表，连续存储容器则需要额外空间）。