浅谈排序网络（一） – 结构

排序一直是算法中十分经典的议题。本文所介绍的排序网络就是解决排序问题的一种抽象结构。本系列预计分三部分，分别介绍排序网络的结构、正确性（设计）和应用。本文为其中的第一部分，主要介绍排序网络的基本结构。

从排序问题说开去

排序问题，简而言之就是将一个输入序列 调整 为 有序 的序列。而其中，有两个关键词十分重要。一是“调整”，也即换序，不难发现，换序可以拆分成最基本的原子操作——两元素交换。另一关键词则是“有序”，有序的一大前提就是两元素间可以比较大小。上面两个关键词揭示了排序最基本的两个操作——比较两元素大小、交换两元素。我们以冒泡排序为例，

for i = 1:n,
    for j = n:i+1,
        if a[j] < a[j-1],
            swap a[j,j-1]
    → invariant: a[1..i] in final position
end

可以看到，仅通过这两个操作就可以完成排序任务了。

不妨再进一步，我们把比较两元素大小、交换两元素两步结合成一个步骤。对于下标i、j，我们比较 a_{i} 、 a_{j} 的大小，并交换元素使 a_{i} \leq a_{j} 。我们称这个复合操作为比较子（comparator）。我们可以用一个对序列的映射来用数学语言描述比较子。比较子即映射 \left[ i:j \right]: A^{n} \rightarrow A^{n} ，满足

\begin{aligned}
\left[ i:j \right]\left( a \right)_{i} &= {\rm min} \left\{ i,j \right\} \\
\left[ i:j \right]\left( a \right)_{j} &= {\rm max} \left\{ i,j \right\} \\
\left[ i:j \right]\left( a \right)_{k} &= a_{k}
\end{aligned}

其中，序列 a \in A^{n} ，下标 k \in \left\{ 0 .. n-1 \right\} ， k \neq i ， k \neq j 。比如对于序列 a = \left\{ 3, 2, 1 \right\} ，有 \left[ 0:2 \right]\left( a \right) = \left\{ 1, 2, 3 \right\} 。

上图中的箭头即代表一个比较子，箭头的方向从下标i到j。

比较子网络

上面的图中出现了两个比较子，它们被安置在数条代表数据的横线上。数据在这些线上从左向右“流动”，每经过一个比较子就（可能）改变一次顺序。这种有确定形式且由比较子组成的网络结构，就是比较子网络（comparator network）。我们可以方便的将其看作若干个比较子的合成。

N = \left[ i_{1}:j_{1} \right]\circ\left[ i_{2}:j_{2} \right]\circ ... \circ\left[ i_{k}:j_{k} \right]

上图就是一个具有4个比较子的比较子网络。

排序网络

之前我们提到过冒泡排序可以只以比较子为原子操作实现，而且无论输入任何数据，冒泡排序的行为都不会发生改变（即由确定的比较子组成）。于是，自然的，我们可以用比较子网络来实现冒泡排序。

因为对冒泡排序中的所有比较子都有 i_{k}<j_{k} ，于是我们可以省略所有同方向的箭头，直接以线段表示比较子。这种具备排序能力的比较子网络就是排序网络（sorting network）。

由于排序网络具有一个固定的结构，所以它的行为不会受输入数据的影响。这就是排序网络的数据独立性。而部分排序比如快速排序，其行为就会因不同的输入数据而改变，由此导致排序效率好坏不一。

另外，由于其结构固定且简单，所以完全可以在不影响其他比较子的情况下调整部分比较子的顺序。比如冒泡排序就可以调整为如下状态。

如果允许并行运算的话，这个排序网络的效率就提高了不少。其复杂度将会从原先的 O\left( n^{2} \right) 降至 O\left( n \right) 。关于并行排序，我会在后续的文章进行进一步说明。

还有一个明显的性质就是，一个排序网络只能适用于固定长度的序列。

稍作休息

这是这个系列文章最短也是内容最少的一篇，算是为后文提供了工具吧。下一篇文章将讨论排序网络的判别与构建。

Reference

1. Sorting network – Wikipedia（ https://en.wikipedia.org/wiki/Sorting_network ）
2. Sorting networks（ http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/networks/sortieren.htm ）