01先把问题说具体
能否预先决定所有比较位置,让同一轮中的很多比较交换同时进行?
02一步步得到方法
数据无关的比较网络
比较网络固定比较哪两个位置以及升降序方向,不根据数据临时决定下一对。双调排序先形成一段升序、一段降序组成的双调序列,再通过分层比较交换合并成统一方向。
本课实现使用二次幂长度。长度 k 从 2 倍增到 n,在每个 k 内,比较距离 j 从 k/2 不断减半。位置 i 的配对位置为 i XOR j,异或翻转对应的二进制位。
一次只交换每一对中的一个方向
i XOR j 会把配对关系映射回来,因此只在 partner>i 时处理。方向由 i 的 k 位确定:该位为 0 的块做升序,反之降序;在最终 k=n 时所有位置的该位为 0,于是整体升序。
固定 k、j 的一轮中,每个位置只出现在一对比较中,彼此互不冲突。下一轮依赖上一轮结果,仍需要同步。
更多工作换取规则结构
n=2ᵐ 时,总比较轮数为 1+2+…+m=m(m+1)/2,每轮 n/2 个比较器,所以工作 O(n log² n),跨度 O(log² n)。
这比比较排序常见的 O(n log n) 工作更多,但访存和比较结构规则,可能适合某些并行小规模场景。不能据此声称它总比归并或快速排序快;重复值稳定性也未得到保证。
03把一个小例子完全算清楚
n=4,输入 [4,1,3,2]。
| 步骤 | 计算与状态 | 为什么这样做 |
|---|---|---|
| k=2、j=1 | [1,4,3,2] | 第一对升序,第二对降序 |
| k=4、j=2 | [1,2,3,4] | 比较相距 2 的位置 |
| k=4、j=1 | [1,2,3,4] | 最终相邻比较完成合并 |
窄屏可左右滑动表格,阅读完整计算与理由。
3 轮,每轮 2 个比较器,得到升序数组。
04为什么这个方法成立
- 双调序列经过相隔半长的比较交换后,较小元素进入前半、较大元素进入后半,两个半段仍具有可递归合并的双调结构。
- 逐层减半比较距离,就把一个双调块合并为有序块。
- 外层倍增构造更大的相反方向有序块,最终完成整个数组升序;这依赖正确的方向位和配对距离。
05把推导翻译成代码
Python · 双调比较网络的串行模拟
def bitonic_sort(values):
a = list(values)
n = len(a)
if n==0:
return a
if n & (n-1):
raise ValueError("power-of-two length required")
k = 2
while k<=n:
j = k//2
while j:
for i in range(n):
partner = i ^ j
if partner>i:
ascending = (i & k)==0
if (ascending and a[i]>a[partner]) or (not ascending and a[i]<a[partner]):
a[i],a[partner] = a[partner],a[i]
j //= 2
k *= 2
return a
print(bitonic_sort([4,1,3,2]))逐个理解关键决定
partner = i ^ j- 通过异或确定本轮唯一配对位置。
partner>i- 每对只比较一次,避免交换后又被反向处理。
(i & k)==0- 同一合并阶段中控制块的升降方向。
06时间、空间与实现范围
工作 O(n log² n),并行跨度 O(log² n);当前 CPU 模拟实际耗时也是 O(n log² n)。
复制输入需 O(n) 空间;网络本身不需要递归栈,不保证稳定排序。
07改变条件,检查哪里会出错
任意长度直接运行
本网络依赖二次幂长度;可补合适哨兵后删除,或选择其他网络。
网络层数就是实际 GPU 延迟
硬件并行度、同步和数据传输仍需测量。
08从手算到独立迁移
先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。
n=8 总共有几轮?
需要一点提示
log₂8=3。
查看解析与答案
1+2+3=6 轮,共 24 个比较器。
i=5、j=2 时 partner 是多少?
需要一点提示
101 XOR 010。
查看解析与答案
7,即二进制 111。
为什么同一轮比较可以同时做?
需要一点提示
检查每个索引出现次数。
查看解析与答案
每个位置恰属于一个互不重叠的配对,不共享写入位置。