排序网络可视化

排序网络说明

什么是排序网络

排序网络（Sorting Network）是一种固定结构的比较网络，通过预定义的比较-交换操作序列对任意输入进行排序。与快速排序、归并排序等自适应算法不同，排序网络的比较顺序与输入数据无关，无论输入什么数据，都执行完全相同的比较操作。

比较器的工作原理

每个比较器连接两条线（位置 i 和 j），将较小的值放上方的线、较大的值放下方的线。如果两个值已经有序，则不做任何操作；如果逆序，则交换。这就是“比较-交换”（compare-and-swap）操作。

深度与并行执行

排序网络的深度（depth）是指从输入到输出需要经过的最大层数。同一深度的比较器之间没有数据依赖，可以同时并行执行。因此深度越小的排序网络排序速度越快。对于 N 个元素，理论最优深度为 O(log N)。

与算法排序的比较

传统排序算法（如快速排序）根据比较结果决定下一步操作，因此比较顺序依赖于输入数据。排序网络则预先确定所有比较操作，这使得它非常适合硬件实现和 GPU 并行计算，但也意味着它不能根据输入特征进行优化。

应用领域

排序网络广泛应用于：GPU 排序（如双调排序是 CUDA 排序的基础）、硬件排序电路设计、安全计算中的“遗忘排序”（Oblivious Sort）、数据库查询优化以及网络数据包排序。在小规模 N（如 N<=32）的情况下，手工优化的排序网络往往比通用算法更快。

已知最优网络

对于小规模 N，已知最优的比较器数量：N=4 需要 5 个比较器、N=5 需要 9 个、N=6 需要 12 个、N=7 需要 16 个、N=8 需要 19 个、N=9 需要 25 个、N=10 需要 29 个、N=16 需要 60 个。0-1 原理证明了只需验证所有 2^N 种二进制输入即可确认网络正确性。