了解荷兰国旗计划

Question

我正在阅读荷兰国旗问题,但无法理解C++实现中函数low和high参数是什么threeWayPartition.

如果我将它们视为要排序的数组的最小和最大元素,那么if和else if语句没有任何意义,因为(data[i] < low)并且(data[i] > high)总是返回零.

我哪里错了？

Answer 1

low并且high是您定义为执行三向分区的值,即执行三向分区,您只需要两个值:

[bottom] <= low  < [middle] < high <= [top]

在C++程序中,您要移动的是分区发生的位置.一步一步的例子:

data = [ 3, 1, 4, 9, 8, 2, 6, 9, 0 ]
low  = 4
high = 8

   [ 3 , 1 , 4 , 9 , 8 , 2 , 6 , 9 , 0 ]
p^  i^                                  q^

   [ 3 , 1 , 4 , 9 , 8 , 2 , 6 , 9 , 0 ]
    p^  i^                              q^

   [ 3 , 1 , 4 , 9 , 8 , 2 , 6 , 9 , 0 ]
        p^  i^                          q^

   [ 3 , 1 , 4 , 9 , 8 , 2 , 6 , 9 , 0 ]
        p^      i^                      q^

   [ 3 , 1 , 4 , 0 , 8 , 2 , 6 , 9 , 9 ]
        p^      i^                  q^

   [ 3 , 1 , 0 , 4 , 8 , 2 , 6 , 9 , 9 ]
            p^      i^              q^

   [ 3 , 1 , 0 , 4 , 9 , 2 , 6 , 8 , 9 ]
            p^      i^          q^

   [ 3 , 1 , 0 , 4 , 6 , 2 , 9 , 8 , 9 ]
            p^      i^      q^

   [ 3 , 1 , 0 , 4 , 6 , 2 , 9 , 8 , 9 ]
            p^          i^  q^

   [ 3 , 1 , 0 , 2 , 6 , 4 , 9 , 8 , 9 ]
                p^         iq^

正如算法所说:

• 交换元件上方的底部(即p + 1),因为底部下面的一切已经被选中,或
• 交换元件下方的顶部(即 q - 1),因为一切之上的顶部已经被选中,或
• 将元素保留在原来的位置,因为它属于中间.

你得到[3, 1, 0, 2],[6, 4]并[9, 8, 9]分别为底部,中部和顶部分区.