并行排序算法与 TopK

双调排序 （Bitonic Sort）

基本介绍

常见的快排、归并排序，比较和交换的位置依赖于数据（谁大谁小要看运行时的值），这个特点很难在 SIMD / 多核硬件上高效并行。

双调排序是一个排序网络（sorting network）——每一步「拿哪两个位置比较-交换」在编译期就完全固定，和数据内容无关。所有比较可以同时做，特别适合 GPU / NPU 这类并行硬件。代价是它的比较次数（\(O(n \log^2 n)\)）比最优的 \(O(n\log n)\) 多，但胜在无数据依赖、可大规模并行。

双调排序了解以下三个操作和特性：
（1）比较-交换（compare-exchange）：取两个位置的元素比一下，按需要交换，使它们满足指定的大小顺序（升或降）。
（2）双调序列（bitonic sequence）：一个「先增后减」或「先减后增」的序列。
（3）任何双调序列，都能用一串位置固定的比较-交换，高效地变成完全有序。 这个「把双调序列拆成有序」的过程叫双调归并（bitonic merge）。

整个双调排序的过程为：

1. 用「相邻小块按升/降交替排序」的方式，把无序数组逐步拼成越来越长的双调序列；
2. 对最终的双调序列做双调归并 → 完全有序。

伪代码与步骤

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

# 把 a[0..n-1] 排成升序，n 必须是 2 的幂
bitonic_sort(a, n, ascending):
    k = 2
    while k <= n:                 # 【外层】k = 正在构建的双调块长度：2 → 4 → 8 → … → n
        j = k / 2
        while j >= 1:             # 【内层】j = 比较距离(stride)：k/2 → … → 1
            for i in 0 .. n-1:    # 每个位置 i 找一个伙伴比一次
                partner = i XOR j            # 伙伴 = 距离 j 的那个位置
                if partner > i:              # 每一对只处理一次
                    up = ((i AND k) == 0)    # 这一对该升还是降，取决于 i 的第 log2(k) 位
                    if ascending == false:
                        up = not up
                    if up:
                        if a[i] > a[partner]: swap(a[i], a[partner])
                    else:
                        if a[i] < a[partner]: swap(a[i], a[partner])
            j = j / 2
        k = k * 2

三重循环：k（块翻倍）、j（距离减半）、i（每个元素比一次）。没有递归、没有依赖数据的分支——比较位置完全由 (k, j, i) 决定，形状确定时编译期即可算死，这就是它能并行的根本原因。

• partner = i XOR j：用异或找伙伴，恰好能配出「距离 j 的一对」,因为比较距离 j 永远是 2 的幂，i XOR j 恰好只翻转 i 的某一个二进制位——这既能把元素两两配成不重复的对，又能保证配对不越过它该在的子块边界。
  设 \(j = 2^b（\)比如 j=2 就是二进制 010，b=1）。i XOR j 的效果是：把 i 的第 b 位翻转，其它位不动。
  • 如果 i 的第 b 位是 0 → i XOR j = i + j（伙伴在右边）
  • 如果 i 的第 b 位是 1 → i XOR j = i - j（伙伴在左边）

• up = ((i AND k) == 0)：决定这一对最终朝哪个方向，靠的是 i 在第 \(\log_2 k\) 位上是 0 还是 1，从而让相邻块自动形成升/降交替。

case 推演

取 a = [3, 7, 4, 8, 6, 2, 1, 5]，n = 8，目标升序。下标记作 0..7。

阶段 k = 2（把相邻 2 个排成交替方向的小双调块，j = 1）

对每对 (i, i^1)，up = (i & 2)==0：

→ [3, 7, 8, 4, 2, 6, 5, 1]

阶段 k = 4（构建长度 4 的双调块）

j = 2，up = (i & 4)==0（i=0,1,2,3 为升；4,5,6,7 为降）：

→ [3, 4, 8, 7, 5, 6, 2, 1]

j = 1：

→ [3, 4, 7, 8, 6, 5, 2, 1]

此时数组是 [3 4 7 8 | 6 5 2 1]：前半升、后半降，整体是一个长度 8 的双调序列。接下来最后一个阶段就是对它做双调归并。

阶段 k = 8（对整个双调序列做归并 → 完全有序）

j = 4（全升，因为 i & 8 == 0 对所有 i 成立）：

→ [3, 4, 2, 1, 6, 5, 7, 8]

j = 2：

→ [2, 1, 3, 4, 6, 5, 7, 8]

j = 1：

→ [1, 2, 3, 4, 5, 6, 7, 8]

TopK：双调排序 + 剪枝

TopK 要「最大的 K 个」，不需要把全部排好。关键观察：

对一个双调序列做一次「距离 n/2 的比较-交换、把较大值留在前半」，会得到两个各自仍是双调的半段，而且前半的每个元素都 ≥ 后半的每个元素。

所以取「最大的 K 个」时：做完这次拆分后，前半（n/2 个）就是较大的一批。只要 n/2 >= K，就可以直接丢掉后半，只在前半继续；反复砍半，直到剩下的规模不足以再砍，再把这一小批排好，取前 K。

核心伪代码

1
2
3
4
5
6
7
8
9
10

bitonic_topk_max(a, n, K):        # 取最大的 K 个
    build_bitonic(a, n)           # 先像双调排序那样把数据拼成一个长度 n 的双调序列
    size = n
    while size / 2 >= K:          # 前半仍装得下 K 个 → 可以砍掉后半
        for i in 0 .. size/2 - 1:
            if a[i] < a[i + size/2]:
                swap(a[i], a[i + size/2])   # 把较大值集中到前半
        size = size / 2           # 丢掉后半，只保留前 size 个
    bitonic_sort(a[0..size-1], size, descending)  # 把存活的一小批排成降序
    return a[0 .. K-1]

和全排序相比，唯一多出来的就是那句 size = size/2——越往后处理的数据越少，这正是 TopK 省算力的地方。

case（K = 4）

沿用上面的 a。先把它构建成双调序列

1

build_bitonic → [3, 4, 7, 8, 6, 5, 2, 1]     （前半升、后半降，双调）

剪枝第 1 轮：size = 8，size/2 = 4 >= K=4，对距离 4 的每对「留大值在前半」：

→ 前半 [6, 5, 7, 8]，后半 [3, 4, 2, 1]。前半正好是最大的 4 个 {5,6,7,8}，后半是最小的 4 个。丢掉后半。

判断是否继续：现在 size = 4，size/2 = 2 < K = 4 → 停止砍半。

收尾：把存活的前半 [6, 5, 7, 8]（注意它是「先减后增」，仍是双调）排成降序：

1

bitonic_sort([6,5,7,8], 4, descending) → Top-4 = [8, 7, 6, 5]

K = 2

同样先得到前半 [6, 5, 7, 8]（size=4）。此时 size/2 = 2 >= K=2，还能再砍一轮：对距离 2 的每对留大在前 → [7, 8, 6, 5] 的前半 [7, 8]，正好是最大的 2 个。之后 size=2，size/2=1 < 2 停止，排降序得 Top-2 = [8, 7]。