顺序统计量¶

线性查找 | Linux C 编程一站式学习

快速排序 | Hello 算法

BFPRT——Top k问题的终极解法 | 知乎@王金戈

无序序列里按名次取出元素, 第 \(k\) 小的那个叫k-th order statistic(顺序统计量). \(k=1\) 是最小, \(k=n\) 是最大, \(k=\lceil n/2\rceil\) 是中位数.

这和按关键字查找不是同一个概念: 后者给一个值, 问在不在表里; 这里给一个名次, 问排完后该位置上是谁. 最直接的办法是先排序再按下标取, 复杂度跟排序走, 比较排序最快也是 \(\Theta(n\log n)\).

找最小¶

\(k=1\). 扫一遍, 记下当前最小, \(\Theta(n)\). 这可以看作是简单选择排序的第一趟, 只是选完不用继续把后面都排好.

以 \(\{8, 3, 9, 2, 5\}\) 为例:

min=8
3 < 8, min=3
9 > 3
2 < 3, min=2
5 > 2
最小是 2, 比较 4 次

有没有比 \(\Theta(n)\) 更快的做法呢?

比较模型下是没有的. 没看过的那个数完全可能是最小的, 漏一个就不能下结论. 这和无序表只能顺序查找同理: 没有有序性, 折半也就无从下手.

找第二小¶

\(k=2\). 仍然无需排序整个表.

只需扫两遍, 先找最小, 再在剩下的里找最小, 大约 \(2n\) 次比较, 仍是 \(\Theta(n)\).

一遍也能做, 可以同时维护min和second两个指针:

8: min=8
3: min=3, second=8
9: 9 比 8 大, 不动
2: min=2, second=3
5: 5 夹在 2 和 3 之间, 不动
第二小是 3

每个元素最多改这两个变量, 还是 \(\Theta(n)\).

更省比较次数的是锦标赛: 两两比, 败者出局, 冠军是最小, 一共 \(n-1\) 次. 第二小只可能出现在「输给过冠军」的那些人里, 最多 \(\lfloor\log_2 n\rfloor\) 个, 再扫这一小撮. 总比较次数 \(n+\lfloor\log_2 n\rfloor-2\), 量级仍是 \(\Theta(n)\).

\(\{5, 2, 4, 7, 1, 3\}\):

(5,2)→2  (4,7)→4  (1,3)→1
        (2,4)→2
        (2,1)→1     最小是 1
输给 1 的: 3 (第一轮), 2 (决赛). min(3,2)=2 即第二小

找第 k 小¶

把前两问里的 \(1\)、\(2\) 换成任意 \(k\), 就是一般的顺序统计量.

先排序再取¶

任选一种内部排序, 取第 \(k\) 个. 正确, 但为了 \(n-1\) 个用不到的相对次序多付了 \(\log n\) 倍. 只查这一次、表又无序时, 往往不值得.

可使用堆进行优化: 建最小堆 \(\Theta(n)\), 再弹出 \(k-1\) 次, \(O(n+k\log n)\). 或者扫一遍维护大小为 \(k\) 的最大堆, \(O(n\log k)\), 堆顶就是第 \(k\) 小. \(k\) 接近 \(n/2\) 时, 仍落到 \(O(n\log n)\) 附近.

快速选择¶

快速排序的 partition 已经把枢轴放到了最终位置: 左边都更小, 右边都更大. 快排接着左右两边都递归; 这里只问第 \(k\) 小, 枢轴要么就是答案, 要么答案只在其中一半.

按照这个思想, 只递归一侧, 就是快速选择.

下面的 \(k\) 约定为排完后的下标 (从 \(0\) 起), 即第 \(k+1\) 小. partition 返回的 mid 正好是这个下标.

int partition(int *arr, int left, int right)
{
    int pivot = arr[left];
    while (left < right) {
        while (left < right && arr[right] >= pivot) {
            --right;
        }
        arr[left] = arr[right];

        while (left < right && arr[left] <= pivot) {
            ++left;
        }
        arr[right] = arr[left];
    }
    arr[left] = pivot;
    return left;
}

/* 从start到end之间找出第k小的元素 */
int order_statistics(int *arr, int start, int end, int k)
{
    /* 用partition函数把序列分成两半，中间的pivot元素是序列中的第i个 */
    int pivot = partition(arr, start, end);
    if (k == pivot) {
        return arr[pivot];
    } else if (k < pivot) {
        /* 从左半部分找出第k-i小的元素并返回 */
        return order_statistics(arr, start, pivot - 1, k);
    } else {
        /* 从右半部分找出第k-i小的元素并返回 */
        return order_statistics(arr, pivot + 1, end, k - pivot);
    }
}

partition与快排的划分完全相同. 和快排的差别只有: 命中 mid 就停, 否则只走包含 \(k\) 的那一侧. Base Case 是枢轴下标恰好等于 \(k\).

以 \(\{5, 2, 4, 7, 1, 3, 2, 6\}\) 找第 \(4\) 小, 即 \(k=3\):

[5  2  4  7  1  3  2  6]     pivot=5, mid=5
 2  2  4  3  1 |5| 7  6      5 是第 6 小, k=3 在左半

[2  2  4  3  1]              pivot=2, mid=2
 1  2 |2| 3  4               这个 2 是第 3 小, k=3 在右半

[3  4]                       pivot=3, mid=3
 |3| 4                       k == mid, 答案 3

全程没有把数组排成 \(1,2,2,3,4,5,6,7\). 丢掉的那一半里, 元素之间的次序可以一直乱着.

算法分析¶

一次 partition 扫完当前区间, \(\Theta(n)\). 总时间和快排一样, 取决于划分是否均匀, 但递归树只有一条路:

• 最好 / 平均: 每次大约砍掉一半, \(T(n)=T(n/2)+\Theta(n)=\Theta(n)\). 写成 \(n+n/2+n/4+\cdots<2n\)

• 最坏: 每次切得极偏 (总拿到最值当枢轴), \(T(n)=T(n-1)+\Theta(n)=\Theta(n^2)\), 和快排退化同形

• 递归栈平均 \(O(\log n)\), 最坏 \(O(n)\); 改成循环后额外空间 \(O(1)\)

• 不稳定, 只适用于顺序表, 原因和快排相同

避免最坏的手段也沿用快排: 随机枢轴 / 三数取中. 最坏也要线性时用下面的BFPRT.

和查找、排序的关系¶

折半查找也是每步丢掉一半, 但前提是表已经有序, 中点下标就能比较. 快速选择的表无序, 必须先花 \(\Theta(n)\) 做 partition, 用枢轴的名次代替有序表的中点.

快排可以看成: 对每个 \(k\) 都做一次选择, 所以两边都要递归, 多出 \(\log n\) 倍. 只要一个名次, 就停在选择.

Top k 问题¶

从长度为 \(n\) 的无序数组里找出前 \(k\) 大 (或前 \(k\) 小). 和第 \(k\) 小不同: 那里只要名次上那一个值, 这里要 \(k\) 个元素组成的集合. 集合内部不必有序. 一旦找出第 \(k\) 大, 再扫一遍就能收齐这 \(k\) 个.

下界仍是 \(\Omega(n)\): 每个元素至少看一眼, 否则漏掉的那个可能挤进前 \(k\).

全排序¶

任选一种内部排序, 取前 \(k\) 个. 比较排序最快也是 \(\Omega(n\log n)\), 因为把不需要的 \(n-k\) 个也排完了.

堆¶

不必整表有序. 两种用法:

• 全体建成大根堆, 弹出 \(k\) 次. 建堆 \(O(n)\), 每次修复 \(O(\log n)\), 合计 \(O(n+k\log n)\). 弹出序列本身有序

• 大小为 \(k\) 的小根堆, 始终装着「目前见到的最大 \(k\) 个」: 先取前 \(k\) 个建堆 \(O(k)\), 后面每个新元素和堆顶比, 比堆顶大就替换并修复, \(O((n-k)\log k)\). 堆里就是前 \(k\) 大, 堆顶是其中最小的那个 (第 \(k\) 大). 前 \(k\) 小则改成大小为 \(k\) 的大根堆

\(k \ll n\) 时两种都接近线性, 已经贴着 \(\Omega(n)\) 下界. \(k=n/2\) (中位数) 时 \(\log k\) 仍是 \(\Theta(\log n)\), 堆方案退回 \(O(n\log n)\).

快速选择法¶

快速选择已经能在平均 \(\Theta(n)\) 里找出第 \(k\) 大. 分界点一旦就位, 大于它的那一侧 (不必再排) 就是前 \(k\) 大. 任意 \(k\) (包括中位数) 平均都是线性; 最坏仍可能 \(O(n^2)\), 随机枢轴后期望 \(\Theta(n)\).

BFPRT¶

快速选择怕的是枢轴总拿最值. 若每次都能拿到中位数, 划分绝对均匀, 就是最好情况 \(\Theta(n)\). 精确中位数和 Top k 是同一量级的问题, 不能先花同样多的时间去求. BFPRT (Blum / Floyd / Pratt / Rivest / Tarjan, 又称 median of medians) 用较小代价造一个不太偏的近似中位数当枢轴, 从而最坏也是 \(\Theta(n)\).

1. 每 \(5\) 个一组 (末组可不足 \(5\)), 组内插入排序, 取出该组中位数, 得到 \(\lceil n/5\rceil\) 个

2. 对这些中位数递归调用 BFPRT, 求出它们的真正中位数 \(x\) (中位数的中位数)

3. 用 \(x\) 做 partition, 之后和快速选择一样只进一侧

\(x\) 至少大于一半小组的中位数; 每个这样的小组里又至少有 \(3\) 个数 \(\geqslant x\) (中位数自己和两个更大的). 粗算至少 \(3n/10\) 个元素可以丢掉, 递归那一侧最多 \(7n/10\):

代入 \(T(n)\le cn\) 得 \(cn/5 + 7cn/10 + an = 9cn/10 + an\), 只要 \(c\ge 10a\) 就有 \(T(n)=O(n)\). 最坏线性.

组大小改成 \(3\): \(T(n)=T(n/3)+T(2n/3)+\Theta(n)\), 代入后多出一项 \(an\), 推不出线性. \(\geqslant 5\) 的奇数都行, \(5\) 组内排序常数最小, 所以选 \(5\).

实践里常数比随机快速选择大很多, 库函数几乎不用纯 BFPRT. Introselect 默认走随机快速选择, 发现规模几乎没按比例下降 (退化成每次只少 \(1\) 个) 再切到 BFPRT; 也可以退化时改切堆选择.

对照¶