Java 中的荷兰国旗问题 | Java 程序对 0、1 和 2 的数组进行排序

荷兰国旗 (DNF) 问题是由著名的荷兰计算机科学家 Edsger Dijkstra 提出的一个最受欢迎的编程问题。顾名思义，它基于荷兰国旗，包含三种颜色，即红、白、蓝。任务是随机排列红、白、蓝三种颜色的球，以便相同颜色的球放在一起。

我们将使用数组来解决上述问题。在这里，我们不使用颜色，而是使用 0、1 和 2，分别代表红色、白色和蓝色。为了匹配球的颜色，我们将对数组进行排序。

例如，考虑以下数组。

输入：{0, 1, 2, 2, 1, 0, 0, 2, 0, 1, 1, 0}

输出：{0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2}

因此，荷兰国旗问题与对 0、1 和 2 的数组进行排序相同。在本节中，我们将为此创建一个 Java 程序。

问题解决方案

有许多解决方案可用，它们在性能和特性上可能有所不同。

朴素方法

简单的解决方案是对数组执行计数排序。在这种排序中，我们计算元素（0、1 和 2）的频率，然后将它们按正确的顺序放置。该方法的缺点是它会遍历数组两次，一次用于排序，一次用于将元素按正确的顺序放置。

为了克服上述缺点，我们重新组织数组，以便在一次遍历中解决问题。它使用一种替代的线性时间分区例程（与三路分区相同），该例程将值分成以下三组。

• 小于基准值（红色）的值。
• 等于基准值（白色）的值，以及
• 大于基准值（蓝色）的值。

算法

让我们通过一个例子来理解。

示例

在以下示例中，我们使用了三个变量 low、mid 和 high。low 和 mid 指针指向数组的开头，high 指针指向数组的末尾。有三种情况：

• 如果 array[mid]=0，则将 array[mid] 与 array[low] 交换，并将两个指针都加一。
• 如果 array[mid]=1，则不执行交换，但 mid 指针会增加。
• 如果 array[mid]=2，则将 array[mid] 与 array[high] 交换，并将 high 指针减一。

考虑以下数组。

最初，low 和 mid 指向数组的开头，即 0，high 指向数组的末尾，即 2。

步骤 1：检查 array[mid]=0，将 array[mid] 与 array[low] 交换，并将两个指针都加 1。

步骤 2：检查 array[mid]=1，无需交换。将 mid 指针加 1。

步骤 3：检查 array[mid]=0, 将 array[mid] 与 array[low] 交换，并将两个指针都加 1。

步骤 4：检查 array[mid]=2，将 array[mid] 与 array[high] 交换，并将 high 指针减 1。

步骤 5：检查 array[mid]=1，无需交换，将指针加 1。

步骤 6：检查 array[mid]=0, 将 array[mid] 与 array[low] 交换，并将两个指针都加 1。

步骤 7：检查 array[mid]=2，将 array[mid] 与 array[high] 交换，并将 high 指针减 1。

我们观察到数组已排序。

让我们用不同的逻辑在 Java 程序中实现上述方法。

荷兰国旗问题 Java 程序

DutchNationalFlag.java

输出

[0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2]

让我们看看相同的另一个逻辑。

DutchFlagProblem.java

输出

Array before Sorting: 
0 0 1 2 0 1 2 
Array after sorting: 
0 0 0 1 1 2 2

上述程序在不使用额外空间的情况下在线性时间内对数组进行排序。数组仅遍历一次。因此，该算法的时间复杂度为 O(n)，其中 n 是数组的大小。