瞭解荷蘭國旗程序

Question

我在讀Dutch national flag problem，但無法理解C++實現中threeWayPartition函數中low和high參數的含義。

如果我認爲他們作爲分和數組的最大元素進行排序，然後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]作爲底部，中部和頂部分區。

Answer 2

} else if (data[i] >= high) {表明你雖然看到了可能不是文章中寫的內容。

Answer 3

對於中間分區中的值，將low和high視爲半開範圍[low,high)。所有小於low的值都會在左側分區中結束。中間分區將包含從low直到但不包括high的值。最後，大於或等於high的所有值都將在右側分區中結束。