Sorting Networks

Aiur · Zellux at 
算法导论第 27 章,在并行处理的条件下效率很高的排序算法。介绍如下面左图所示,每条横线(wire)代表一个待 比较的数值,竖线(comparator)表示连接的两条横线要做一次比较,并将较小的值放在输出横线的上方,较大的放在下面。排序过程就是从左往右依次 调用各个 comparator(在同一位置上的 comparator 可以同时做)有图表示了四个数字 3, 2, 4, 1 在经过这个 Sorting Network 时的行为。(由于背景为深色,建议点击图片查看)下图是一个冒泡排序的 Sorting Network 表示可以看到所有的比较都没有并行,效率很低。接下来先介绍一个 0-1 原理……