时间戳

首页 > 解决方案 > Dijkstra 分区算法：特例

algorithm - Dijkstra 分区算法：特例

问题描述

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

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

标签： algorithmsortingpartitioninganalysisdutch-national-flag-problem

解决方案

正如@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 之间循环i并j-1排序 W 和 B。

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

推荐阅读