概述
k-sorter 问题指如何利用“给 k 个元素排序”这一基本操作,构造高效的排序算法。由于一个 k-sorter 可以由 $k\log k$ 次比较操作构造,而比较排序的时间复杂度下界是 $n\log n$,因此 k-sorter 问题的排序器使用次数下界(下称比较下界)为 $n\log n/k\log k$。我对这个问题的了解来自于清华大学邓俊辉老师的《数据结构》课程中的一道编程练习题(题目对应 $k=3$ 的情景),并将一个简单的做法($n\log n/k$ 次比较的算法)出做了集训队作业题目1。近期我对此问题又做了一些调查和探索,结论如下:
- 存在若干种比较次数在 $O(n\log n/k)$ 的确定性排序算法,包括两个比较简单的基于归并的算法;
- 存在期望 $O(n\log n/k\log k)$ 次比较的随机算法,这一算法思路简单,但分析稍加繁琐;
- 存在 $(n\log n/k\log k)$ 次比较的确定性算法,这一算法来自2.
两种简单算法
我们首先介绍两种比较次数为 $O(n\log n/k)$ 的简单算法。
算法1:二路归并
算法流程:考虑使用二路归并算法。首先将所有元素划分为等大的两部分递归排序,并在两序列末尾分别补上 $k/2$ 个无穷大 INF。接下来不断地如此做:在两个序列中分别选择 $k/2$ 个最小的数,将这些数排序,并将其中最小的 $k/2$ 个元素从队列中取出,直到除 INF 外的所有元素均被取出。
正确性:只需证明每次取出的 $k/2$ 个元素是整个序列最小的 $k/2$ 个元素即可,为此只需证明两序列最小的 $k/2$ 个元素的并包含了整个序列最小的 $k/2$ 个元素,而这是显然的。
比较次数:设 $T(n)$ 为比较次数,有 $T(n) = 2T(n/2) + O(n/(k/2))$,用主定理解得 $T(n) = O(n\log n/k)$。
算法2:$2^{k-1}$ 路归并
算法流程:首先将整个序列随意划分成 $2^{k-1}$ 个等大的部分递归排序,现在考虑如何合并这些序列。考虑建立一棵区间长度为 $2^{k-1}$ 的、维护区间最小值的线段树,其中位置 $i$ 维护划分成的第 $i$ 个序列中,未被取出的最小元素值。很明显,线段树的根节点便维护了所有 $2^{k-1}$ 路中所有元素的最小值(因为每个序列本身已经排序)。
考虑每次从线段树中取出最小元素以构成完整的、排序后的序列。不妨设当前全局最小值 $u$ 来自第 $i$ 个序列。在取出 $u$ 后,我们需要将线段树的位置 $i$ 更新为序列 $i$ 去掉 $u$ 后最小的元素。由于更新线段树上一个结点仅会影响这个结点到根上的所有结点 $i, parent(i), parent(parent(i)),\dots $,而这些结点的信息仅和
共 $k$ 个元素的相对大小有关,因此可以用一个 $k$-sorter 比较操作完成更新。
正确性:正确性是显然的。
比较次数:设 $T(n)$ 为比较次数,有 $T(n) = 2^{k-1}T(n/2^{k-1})+O(n)$,用主定理解得 $T(n) = O(n\log n/k)$。
类似快速排序的随机算法
算法流程
为了描述的方便不妨设我们拥有 $2k$-sorter 比较器。首先从所有元素中随机选出 $k$ 个支点,将他们用 1 次比较操作排序,并用 $O(n/k)$ 次比较操作将剩余 $n-k$ 个元素划分到这 $k$ 个元素之间,并递归对 $k+1$ 段进行排序。这一步可以通过每次将 $k$ 个元素和 $k$ 个支点共同排序来完成。
比较次数分析
由于分析过程复杂,这里仅列出一些关键的引理,证明的细节在附件 proof.pdf 中给出。
引理1:
引理2:当 $n>k>1$ 时,有
引理3:算法的比较次数可以表示为
引理4:
引理5:
定理:多路快速排序算法的期望比较次数是 $O(n\log n/k\log k)$。
证明思路:考虑使用代入法,将 $cn\log n/k\log k$ 带入引理 4 并对和式进行估计。对于第二部分直接用 $\log n$ 作为 $\log i$ 的上界并用引理 2 计算,第一部分将和式分为 $[1, B]$ 和 $[B, n-2]$ 两部分,并分别用 $\log B$ 和 $\log n$ 作为 $\log i$ 的上界,取 $B = n/k$,利用引理 $1, 2, 5$ 进行估计。
注记
这一部分的分析是我自己折腾出来的,awd/wmd/WerkeyTom_FTD/tqyaaaaang 等同学帮助 fix 了一些问题。
文献2中给出了另外一种基于快速排序的实现:不断随机选择划分点,直到每一部分包含不超过 $2n/(k/2\ln k\log k)$ 个元素。
确定性算法
这一算法来自 2
子算法 1
使用 $k$ 元比较器,在 $O(n/k)$ 次比较操作选出第 $i$ 大元素。
考虑将经典的 Median of medians 算法3推广到 $k$ 元比较器上,这一点是容易的:将原先算法中分为 5 路变为 $k$ 路即可。
算法流程
算法分为四步。设 $a, b$ 为待取的常数。
- 将序列随意划分为 $n/k$ 个长度为 $k$ 的链,并对每个链排序;
- 从每个链中选出均匀的选出 $a$ 个元素,即选出排名为 $k/a, 2k/a, \dots$ 的元素,将所有链中选出的元素称为 $a$-points
- 从所有 $a$-points 中均匀的选出 $b$ 个元素,称为 $b$-points
- 将所有元素划分到 $b$-points 之间,递归给所有的段排序
算法分析
首先分析划分过程的复杂度。
- 第一步需要 $n/k$ 次比较
- 第二步不需要比较操作
- 第三步通过连续 $b$ 次使用子算法,需要 $O(\frac{nab}{k^2})$ 次比较。
- 第四步仅需要 $O(n/k)$ 次比较
取 $a = b = \frac {\sqrt k}{\log k}$,便可以将第三步的比较次数限制在 $O(n/k)$ 之内。
然后分析划分的平均程度。
引理:划分出的任何一段元素数量都不超过 $n(2/b+1/a)$。
证明:不妨将所有 $a$-points 从小到大列出,由于 $b$-points 是均匀选出的,任意两个 $b$-points 中均有 $O(na/(kb))$ 个 $a$-points。考虑原序列中,大小在某两个相邻的 $b$-points $b’ < b’’$ 之间的元素个数。由于任何一个元素均在两个相邻的 $a$-points 之间,我们只需要考虑所有相邻的 $a$-points $a’<a’’$ 的情况。
两个 $a$-points 至少有一者在 $b’, b’’$ 之间,由于其之间共有 $\frac{na}{kb}$ 个 $a$-points,这种情况仅有不超过 $\frac{2na}{kb}$ 对,因此这些 $a$-points 之间对应的原数组的元素个数之和为
$a’ < b’ < b’’ < a’’$,由于 $a’$ 和 $a’’$ 在其对应的链上是连续的,因此在每一个链上至多有一对这样的 $a$-points,总的对数不会超过链的个数 $n/k$,之间的元素个数不会超过
综上所述,任何两个 $b$-points 之间的元素个数都不超过 $n(2/b +1/a)$。
Q. E. D.
由于 $a = b=\sqrt k/\log k$,算法可以在 $O(n/k)$ 的时间复杂度内,将所有元素划分到 $b+1 = O(\sqrt k/\log k)$ 组中,并使得每组中元素都不超过 $3n/b$ 个元素。因此比较次数可以如下表示
其中 $d_i$ 是第 $i$ 段中包含的元素个数,有 $d_i\le 3n/b$。那么用代入法就有
取 $c = c_1/c_2$ 便能够使得归纳成立。
参考
1. http://uoj.ac/problem/445 ↩
2. Beigel R, Gill J. Sorting n objects with a k-sorter[J]. IEEE Transactions on Computers, 1990, 39(5): 714-716. ↩
3. https://en.wikipedia.org/wiki/Median_of_medians ↩