双调排序（排序网络）

经典排序算法 · 比较器网络 · 深度 O(log²n)，可并行

一张写死的「排序电路」

前面 15 个排序都是程序：看数据、做判断、决定下一步。双调排序是另一个物种——排序网络：一张固定的「电路图」，n 条水平线（wire）上按固定位置放比较器（连接两条线，把小值送一端、大值送另一端）。比较器的位置与顺序在排序开始前就定死，与数据完全无关。正因如此，同一列的比较器互不相干、可以同时执行——这是 GPU 和硬件排序的思想根基。

先造双调，再合并

双调序列指「先升后降」（或其循环移位）。网络分两阶段：构造——递归地把前半排成升序、后半排成降序，拼在一起就是双调；双调合并——对双调序列做一轮距离 n/2 的成对比较交换，它会神奇地裂成两个双调半区、且前半整体 ≤ 后半，距离减半递归下去就全有序。n=8 展开后是 6 列、24 个比较器：总比较次数 O(n log²n) 比快排多，但每列并行，墙钟时间只有 6 拍。

下面固定输入 [5,2,7,1,8,3,6,4]。点「下一步」逐列看：8 条水平线左端标着当前值，比较器竖线上的小三角指着大值要去的方向；琥珀是正在执行的列（4 个比较器同时动）、绿色是已执行的列。走完第 3 列（列 2），序列变成 [1,2,5,7,8,6,4,3]——升到 8 再降，完美双调；后 3 列距离 4→2→1 合并，第 6 拍全有序。右侧代码随每一步同步高亮。

这是一张固定的「排序网络」：24 个比较器排成 6 列，位置与数据无关——同一列的比较器互不相干，可以并行执行

1function bitonicSort(a: number[]): void {
const n = a.length;                        // n 为 2 的幂
for (let k = 2; k <= n; k *= 2) {          // 阶段：构造长度 k 的双调段
  for (let j = k >> 1; j >= 1; j >>= 1) {  // 一列：比较距离 j（同列可并行）
    for (let i = 0; i < n; i++) {
      const l = i ^ j;                     // 与 i 距离 j 的伙伴
      if (l > i) {
        const asc = (i & k) === 0;         // 该段方向：升 or 降
        if (asc ? a[i] > a[l] : a[i] < a[l])
          [a[i], a[l]] = [a[l], a[i]];     // 比较交换（比较器）
      }
    }
  }
}
15}

n / 列数8 / 6

并行深度log²n 级 = 6 拍

1 / 8

为什么值得多做几次比较

数据无关：比较器序列固定 → 无分支、无随机访存，天生适合硬件/SIMD/GPU。
并行深度：同列并行，总深度 log n·(log n+1)/2 列 = O(log²n) 拍。
双调合并：距离 n/2 的一轮比较把双调裂成「有序的两个双调半区」。
0-1 原理：只要网络能排好所有 0/1 序列，就能排好任意序列——排序网络的正确性基石。

对比一下：快排在 CPU 上无可匹敌，但它的分支和数据依赖让 GPU 难受；双调排序多做常数倍比较，换来完全规整的并行结构，是显卡排序、外部归并预排序的常客。同族的还有 Batcher 奇偶归并网络（比较器更少）与理论上 O(log n) 深度的 AKS 网络（常数巨大，纸面冠军）——「排序」这件事，在并行世界里有一套自己的谱系。

算法可视化

双调排序（排序网络）

一张写死的「排序电路」

先造双调，再合并

为什么值得多做几次比较