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

文章目录[隐藏]

• 从排序问题说开去
• 比较子
• 比较子网络
• 排序网络
• 性质
• 稍作休息
• Reference

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

从排序问题说开去

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

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）