Dijkstra 分区算法:特殊情况

Question

我一直在探索Dikstra分区算法。以下是我给出的：

R = Red
W = White 
B = Blue

我有这个未分区的阵列。

| W | B  | R |  W  | R  | W | B |  W  |  W | 

我希望它以以下格式连续分区：R，W，B。

| R  |  ?  | W  |  B |
0    i     j    k    n

鉴于：

i = 0
j = n
k = n
n = number of elements

以下是我的算法：

while  (i < j)
{
case a[i]:
R : i++;
W : j--; swap(a[i], a[j]);
B : j--; k--; swap(a[i], a[k]); swap(a[i], a[j]);
end case 
}
//Done Sorting

输出应如下所示：

|  R  | R  | W  |  W  |  W  |   W  |  W  |  B  |  B |

我的问题是：

1. 我可以减少掉期次数吗？如果是，如何？
2. 如果有 4 种颜色要分区，该算法是否适用？

谢谢。我真的需要理解这个概念。

Answer 1

正如@m69给出的线索，这是Dutch National Flag问题。

基于取自维基百科的伪代码：

A : array of values
i ← 0
j ← 0
n ← size of A - 1
while j ≤ n:
Case A[i]:
R:
swap A[i] and A[j]
i ← i + 1
j ← j + 1
B:
swap A[j] and A[n]
n ← n - 1
W:
j ← j + 1

请注意，在本例中，在 B 情况下，您少了 1 个隔夜利息。

对于你的第二个问题：是的。最简单的方法是将 2 个中间部分视为相同，然后在数组上再次运行并仅对这 2 个进行排序。

假设您有 4 种颜色：R, W, B, G并且您想按该顺序对它们进行排序。所以第一步：在你的开关情况下有W or B:.完成后运行算法，在你的数组上运行，并找到第一个 W 或 B 的索引(称为 i(和第一个 G 的索引(称为 j(。现在您所需要的只是在i和j-1之间循环，并对 W 和 B 进行排序。

整个过程可以在 O(n( 中完成。