β

双调排序

炒饭的小站 26 阅读
浏览人数: 613

双调排序是一种并行排序算法,如果以串行的方式运行,其复杂度为 O(n\log^2n) ,相对地,如果有 n 个可同时运行的线程,则复杂度为 O(\log^2n)

首先介绍双调序列。所谓单调序列,就是指一个递减或者递增序列,而双调,就是将两个长度相同,单调性相反的序列连接起来的序列,如果画成图形就是以下两种序列:

p1

对于这样一个序列,可以设计一个输入和输出个数为 2^k 的排序网络,对 2^k 个数进行排序,其网络结构如下:

p2

这个网络共有16个输入,其中每一条连线代表一次比较。可以看出,输入为 2^k 的排序网络总共有 k 个部分,第 i 个部分完成对规模为 2^{k-i+1} 的数据的比较。

首先,输入第一部分的序列是一个先增后减的双调序列,第一部分的比较网络会将这个序列分为两个子序列,而且前半部分子序列中的每一个数都小于后半部分中的数,这是由比较前两个子序列的单调性决定的。

然后,比较网络的第二部分对上回输出的每个子序列再次进行相同的操作。网上好多人都说因为这个序列仍然是双调的所以继续下去,双调性可以保持云云,但这个说法是完全错误的!因为再进行下去的序列完全有可能变成不是双调的。(不过下面有评论说我双调的定义有误,所以双调性其实可以保持)下面举个例子说明:

其中出现了(12 11 13 12)这个非双调的序列,但是结果正确。网上流行的“每个子序列都是双调序列”的说法完全是错误的。

阅读《算法导论》,发现正确性证明确实是用到了保持双调性的性质,但是并非直接得到。

引理:对于单调增函数 f(x) ,若任意比较网络输入 <x_1,x_2,\cdots,x_n> 时,输出 <x_{k_1},x_{k_2},\cdots,x_{k_n}> ,则输入 <f(x_1),f(x_2),\cdots,f(x_n)> 时,会输出 <f(x_{k_1}),f(x_{k_2}),\cdots,f(x_{k_n})>

证明:因为 f(x) 单调增,所以通过比较网络中某一比较器时,若 x_1>x_2 ,则 f(x_1)>f(x_2) ,反之亦然。

定理:对于排序网络来说,只要可以对0,1序列进行排序,即可对任意序列排序。

证明:若排序结果(递减排序)出现了 a_i>a_ja_ia_j 之前的情况,那么定义 f(x)=0, x<a_i; f(x)=1, x\geq a_i ,使用上述引理得出这个网络不能给0,1序列排序。矛盾。

所以我们只需要证明双调排序对0,1序列有效即可,而对于0,1序列,易证明经过每一部分之后的子序列总是可以保证双调性的,从而证明了排序是有效的。

那么如何从无序序列得到双调序列呢?可以使用排序的方式。因为长度为2的序列一定是双调序列,通过构造以下的网络,就可以完成从无序序列到双调序列的转换:

p3

其中灰色的比较器表示比较方向和白色的比较器相反,这样才可以形成一个反向有序的序列。

至此,双调排序已经完整说明。

作者:炒饭的小站
随意而为,不拘一格
原文地址:双调排序, 感谢原作者分享。

发表评论