我正在阅读 Dutch national flag problem , 但不明白 low
是什么和 high
参数在 threeWayPartition
中C++实现中的函数。
如果我假设它们是要排序的数组的最小和最大元素,那么 if
和 else if
自 (data[i] < low)
以来的陈述没有任何意义和 (data[i] > high)
始终返回零。
我哪里错了?
最佳答案
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]
作为分别为底部、中间和顶部分区。
关于algorithm - 了解荷兰国旗计划,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/11214089/