了解荷兰国旗计划

Question

我正在阅读荷兰国旗问题，但无法理解C实现中的三Way分区函数中的低和高参数是什么。

如果我假设它们是要排序的数组的最小和最大元素，那么if和其他if语句没有任何意义，因为（data[i]

我哪里错了？




Answer 1

将低和高视为中间分区中值的半开放范围 [低、高）。 所有小于低值的值都以左侧分区结束。中间分区将包含从低到高（但不包括）的值。最后，所有大于或等于 high 的值都位于正确的分区中。

Answer 2

} else if （data[i]

Answer 3

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^

正如算法所说：

• 交换底部上方的元素（即p1），因为底部下方的所有元素都已被检查，或者
• 交换顶部以下的元素（即q-1），因为顶部以上的所有元素都已被检查，或者
• 保留元素，因为它属于中间

您将[3,1,0,2]、[6,4]和[9,8,9]分别作为底部、中间和顶部分区。