0

我一直在探索 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 种颜色,该算法是否适用?

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

4

1 回答 1

2

正如@m69 给出的线索,这就是Dutch National Flag问题所在。

基于取自Wikipedia的伪代码:

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)。现在你只需要在 and 之间循环ij-1排序 W 和 B。

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

于 2018-08-09T19:57:50.713 回答