冒泡排序 每执行一次外层循环, 当前最大的数就会下沉到数组末尾. 很简单, 但效率低下. 复杂度 `O(n^2)`.
插入排序
第 i 步循环时, 子数组 L[0..i-1]已经有序, 只需将
L[i] 插入到合适位置.
时间复杂度 `O(n^2)`.
当 L 初始即有序时, 时间复杂度为 `O(n)`.
Shell 排序 时间复杂度优于 `O(n^2)`. 它由插入排序改造而来, 隐含的常数很小, 往往有不俗的成绩.
快速排序
次序统计量 求第 k 小的元素 (最小的元素是第 0 小). 和快速排序使用相同的 partition 子过程. 但分治时只走一个分支, 平均时间复杂度为 `O(log 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 占空间较大时,
可以只排序指向记录的指针表 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()