双调排序

双调排序

本站内容版权属于本人。转载须告知本人,写明出处,并在文首提供指向本站对应文章的链接。
本文链接:双调排序

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

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

p1

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

p2

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

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

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

  • 初始值:(10 11 13 14 15 16 17 18 19 15 13 12 12 11 9 8)
  • (10 11 13 14 15 16 17 18) (19 15 13 12 12 11 9 8) 网络1排序→ (10 11 13 12 12 11 9 8) (19 15 13 14 15 16 17 18)
  • (10 11 13 12) (12 11 9 8) (19 15 13 14) (15 16 17 18) 网络2排序→ (10 11 9 8) (12 11 13 12) (15 15 13 14) (19 16 17 18)
  • (10 11) (9 8) (12 11) (13 12) (15 15) (13 14) (19 16) (17 18) 网络3排序→ (9 8) (10 11) (12 11) (13 12) (13 14) (15 15) (17 16) (19 18)
  • 最终结果:(8 9 10 11 11 12 12 13 13 14 15 15 16 17 18 19)

其中出现了(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

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

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

双调排序”有2条评论

  • 谢小帅

    网络上说法也没错,因为定义是这样的:
    (1)存在一个 ak(1≤k≤n),使得 a1 ≥ … ≥ ak ≤ … ≤ an 成立;或者
    (2)序列能够循环移位满足条件(1)
    那么 12 11 13 12 循环位移之后为:11 13 12 12 也是双调序列,就像初始值给出的一样。

    回复
    • 炒饭 帖子作者

      学习了。
      如果是这样的话,这个说法确实能够说通。不过证明起来,可能会更加复杂吧。

      回复

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据