内排序

`O(n^2)` 的算法

冒泡排序 每执行一次外层循环, 当前最大的数就会下沉到数组末尾. 很简单, 但效率低下. 复杂度 `O(n^2)`.

插入排序 第 i 步循环时, 子数组 L[0..i-1]已经有序, 只需将 L[i] 插入到合适位置. 时间复杂度 `O(n^2)`. 当 L 初始即有序时, 时间复杂度为 `O(n)`.

Shell 排序 时间复杂度优于 `O(n^2)`. 它由插入排序改造而来, 隐含的常数很小, 往往有不俗的成绩.

`O(n log n)` 的算法

快速排序

次序统计量 求第 k 小的元素 (最小的元素是第 0 小). 和快速排序使用相同的 partition 子过程. 但分治时只走一个分支, 平均时间复杂度为 `O(log n)`.

`O(n)` 的算法

链式基数排序 对 N 个 RADIX 进制的 KEYS 位数进行排序, 这些数字的每一位数放在数组 key 中, 以 next 指针链接起来. 算法按低位优先格式依次对各关键字进行分配和收集, 经过 KEYS 轮排序后完成. 

smallint key[N+1][KEYS] # 关键字, 取值为 0..RADIX-1
int next[N+1]       # 下一结点的下标
int first[RADIX]      # RADIX 个子表的头
int last[RADIX]       # RADIX 个子表的尾

# 按第 i 位数将各数字链成 RADIX 个子表, 每个表中 key[*][i] 值相同
# first[j], last[j] 指向各子表的第一个和最后一个记录
distribute(i):
  # 清空 RADIX 个子表
  for j = 0 to RADIX-1:
    first[j] = 0
  # 从头结点起遍历静态链表, 将结点打散重新链接
  p = next[0]
  while p:
    d = key[p][i]     # 取出第 i 位数
    if first[d]:      # 当第 d 个子表不空
      next[last[d]] = p # 接到子表尾
    else:
      first[d] = p    # 作为子表头
    last[d] = p       # 更新子表尾指针
    p = next[p]

# 按分配结果依次链接各子表
collect(i):
  tail = 0
  for j = 0 to RADIX-1:
    if first[j]:
      next[tail] = first[j]
      tail = last[j]
  next[tail] = 0

radix_sort():
  # 静态链表初始化, 下标 0 为头结点
  for i = 0 to N-1:
    next[i] = i+1
  next[N] = 0
  # 从低位至高位进行排序
  for i = 0 to KEYS-1:
    distribute(i)
    collect(i)

外排序

最少交换次数

对一个数组 L[n] 进行排序, 假定我们已经知道第 i 个元素应该移动到 sigma(i) 的位置. 那么最少交换次数是多少? 具体方案是怎样的?

    定义如下概念: 回到原问题. `i mapsto sigma(i)` 确定了 `n` 个元素的置换 `sigma`. 首先将它分解为不相交轮换的乘积: `sigma = c_1 cdots c_s`. 再将每个轮换分解为对换.
    事实上, `k`-轮换 `(i_1 cdots i_k)` 可以分解为 `k-1` 个对换: `(i_1 i_2) cdots (i_(k-1) i_k)`, 运算从右往左进行. 因此所有 `s` 个 `k` 轮换分解为 `n-s` 个对换. 下面证明至少需要交换 `n - s` 次.
  1. 注意以下事实: `k ge 2` 时, 把 `k`-轮换中两个元素对换, 效果是将它分解为两个不相交轮换. 反之, 两个不相交轮换中各取一个元素, 将它们对换, 效果是合成一个大的轮换.
  2. 下证每个 `k`-轮换最少可以分解为 `k-1` 个对换. 结论对 `k = 1` 显然. 假设 `k gt 1`, 且结论对一切小于 `k` 的正整数成立. 考虑 `k`-轮换的情形, 交换两个不同元素后, 它被分解为更小的两个轮换, 设它们的长度分别为 `k_1, k_2`, 则 `k_1 + k_2 = k`, 由归纳假设, 这两个轮换最少分解为 `k_1 - 1`, `k_2 - 1` 个对换, 因此原来的 `k`-轮换可以分解为 `(k_1 - 1) + (k_2 - 1) + 1` `= k - 1` 个对换. 这个方案也是最少的, 因为不可能将 `k`-轮换中的元素与不在其中的元素交换, 这将引入其它元素.
  3. 下证集合 `[1..n]` 上的 `s` 个不相交轮换最少可以分解为 `n-s` 个对换. 当 `s = 1` 时, 由 2. 知道结论成立. 假设结论对一切小于 `s` 的正整数成立, 此时我们的分解方案是仅交换每个不相交轮换的内部元素, 这将把它们分解为 `n-s` 个对换. 假如方案的第一步交换了两个不相交轮换之间的元素, 这将减少一个轮换数目, 剩下 `s-1` 个轮换. 由归纳假设, 它最少分解为 `n-s+1` 个对换, 不是最少的方案.

地址排序 原记录表 L 占空间较大时, 可以只排序指向记录的指针表 adr, 再通过地址排序调整原记录的位置. 下面假设 adr 给出了 L 中元素的次序, 即 L[adr[i]], i = 0..L.length-1 是 L 的一个单调增序列. 算法实际上将各个静态循环链表逆向调整了一个位置. 

rearrange(L, adr):
  for i = 0 to L.length-1:
    if adr[i] != i:   # 没有归位, 需要调整
      j = i
      tmp = L[j]
      k = adr[j]
      do:
        L[j] = L[k]
        adr[j] = j  # 作标记, 表示已经归位
        j = k
        k = adr[k]
      while k != i
      L[j] = tmp
      adr[j] = j

败者树

败者树 

int loser[N]            # loser[1] 是根结点, loser[0] 是冠军
int leaf[N+1]           # leaf[N] 作特殊用途, 见 init()

# 从 leaf[i] 出发向上调整, 败者留在结点中, 胜者向上继续比赛
adjust(i):
    p = (N+i+1) >> 1    # 求父结点下标
    while p:
        if leaf[i] > leaf[loser[p]]:
            swap(i, loser[p])
        p >>= 1
    loser[0] = i        # 选出冠军

init():
    # 在虚拟结点中存储"负无穷大", 让所有的 loser 指针指向它
    leaf[N] = -INF
    for i = 0 to N-1:
        loser[i] = N
    # 从后往前依次读入记录, 并调整叶子结点
    for i = N-1 downto 0:
        input(leaf[i])      # 读取输入, 该路已无数据时, 得到 INF
        adjust(i)
    # 调整 N 次后, 产生第一个冠军

# 利用败者树将 leaf[0..N-1] 的记录进行 N 路归并
N_merge():
    init()
    # 每输出一个冠军, 就读入新的记录代替它, 直到没有新数据
    i = loser[0]
    while leaf[i] != INF:
        output(leaf[i])
        input(leaf[i])
        adjust(i)
        i = loser[0]

败者树构建过程示意. 下面圆括号代表 loser 结点, 方括号代表 leaf 结点.
从上而下, 从左而右, loser 结点和 leaf 结点的下标分别是 0, 1, 2, ...
为直观起见, loser 结点上写的是值而不是指针.

       ( )            ( )            ( )            ( )
        |              |              |              |
       ( )            ( )            ( )            (3)
      /   \          /   \          /   \          /   \
    ( )   ( )      (2)   ( )      (2)   (9)      (2)   (9)
   /   \  /  \    /   \  /  \    /   \  /  \    /   \  /  \
  (7) [ ][ ][ ]  (7) [ ][ ][ ]  (7) [ ][ ][9]  (7) [ ][3][9]
  / \            / \            / \            / \
[ ][7]         [2][7]         [2][7]         [2][7]

       (2)
        |
       (3)
      /   \
    (5)   (9)
   /   \  /  \
  (7) [5][3][9]
  / \
[2][7]

置换-选择排序 

int loser[N]    # 败者树
int key[N]      # 关键字, 放在败者树的叶结点
int tag[N]      # 归并段号
int cur_tag = 1 # 当前段号
int max_tag = 1 # 最大段号

lose(i, j):
    return tag[i] > tag[j]\
        or (tag[i] == tag[j] and key[i] > key[j])

adjust(i):
    p = (N+i+1) >> 1
    while p:
        if lose(i, loser[p]):
            swap(i, loser[p])
        p >>= 1
    loser[0] = i

init():
    for i = 0 to N-1:
        tag[i] = key[i] = loser[i] = 0
    for i = N-1 downto 0:
        if input(key[i]):
            tag[i] = cur_tag
        else:
            tag[i] = max_tag + 1
        adjust(i)

# 求下一归并段
next_segment():
    w = loser[0]                # w = winner
    while tag[w] == cur_tag:    # 选得的冠军属于当前段时
        key_to_put = key[w]
        output(key_to_put)
        if !input(key[w]):      # 输入文件结束, 虚设段号为 max_tag + 1
            tag[w] = max_tag + 1
        elif key[w] < key_to_put:    # 读入数据较小, 应属于下一段
            max_tag = cur_tag + 1
            tag[w] = max_tag
        adjust(w)
        w = loser[0]
    output(SEGMENT_DILIMITER)   # 将段结束标志写入输出文件
    cur_tag = tag[w]

replace_select_sort():
    init()
    while cur_tag <= max_tag:
        next_segment()