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

荷兰国旗问题在看似简单的数组排序任务中增加了一个既迷人又实用的转折。想象一个只有 0、1 和 2 的数组，类似于荷兰国旗的红、白、蓝三色。这项奇特的工作要求我们对这些元素进行排序，使所有的 0 聚集在左边，所有的 1 聚集在中间，所有的 2 聚集在右边。在 Python 编程领域，我们可以通过一种称为荷兰国旗算法的复杂方法来实现这一点。本文将解释这个问题的复杂性，并引导你完成一个 Python 解决方案，该解决方案在清晰度和有效性之间取得了平衡。那么，让我们开始掌握荷兰式排序的艺术吧！

荷兰国旗问题

虽然排序一个只有 0、1 和 2 的数组可能看起来很简单，但它可能相当有挑战性。为了纪念荷兰国旗鲜艳的条纹，我们将这个谜题称为“荷兰国旗问题”。想想红、白、蓝这三种颜色。我们的目标？高效地将 0、1 和 2 按此顺序放置在数组中。本质上，我们希望所有的 0 都在前面，然后是 1，最后是 2。将其视为在我们的 Python 数组中规划一场颜色游行！

问题

考虑以下数组：[0, 1, 2, 1, 0, 2, 1]。你的任务是修改这个数组，使其看起来像 [0, 0, 1, 1, 1, 2, 2]。看出规律了吗？我们正在将颜色分组，以模仿荷兰国旗的条纹：所有的 0 放在一起，然后是 1，然后是 2。尽管这个问题看似简单，但它很复杂，并且有一个巧妙的 Python 解决方案。

解决荷兰国旗问题的双指针算法

想象你有一个包含三个数字 0、1 和 2 的数组。目标是排序这个数组，使所有的 0 都出现在前面，然后是所有的 1，最后是所有的 2。

我们采用一种先进的方法，通过跟踪三个指针来实现这一点

• 低指针 (low)：此指针用于跟踪数组中下一个 0 应该去的位置。
• 中指针 (mid)：中指针有助于在数组元素之间导航。每个元素都会被检查是否为 0、1 或 2。
• 高指针 (high)：高指针指定数组中下一个 2 应该放置的位置。

算法的步骤如下：

• 初始化低指针指向数组的开头（索引 0），中指针也指向开头，高指针指向数组的末尾（索引 len(arr) - 1）。
• 开始一个循环，直到中指针小于或等于高指针。
• 在循环内部，检查中指针指向位置的元素。
• 如果它是 0，则将其与低指针指向位置的元素交换。这有效地将 0 移到数组的开头，并同时递增低指针和中指针。
• 如果它是 1，则将中指针向前移动一个位置，因为 1 应该放在已排序数组的中间。
• 如果它是 2，则将其与高指针指向位置的元素交换。这会将 2 放在数组的末尾，并递减高指针。

继续执行这些步骤，直到中指针不再小于或等于高指针。

此函数返回一个已排序的数组，其中所有 0 都在开头，然后是所有 1，最后是所有 2。该方法以 O(n) 的时间复杂度有效地重新排列元素，其中 n 是数组的长度。

因此，荷兰国旗算法，其灵感来自荷兰国旗的颜色，能够像一场组织得井井有条的游行一样，编排 0、1 和 2 数组的排序。

示例数组 [0, 1, 2, 1, 0, 2, 1]

1. 初始化指针：我们从三个指针开始：low、mid 和 high。low 指向数组的开头（索引 0），mid 也从开头开始，high 指向数组的末尾（索引 6）。
   • 数组：[0, 1, 2, 1, 0, 2, 1]
   • low：0，mid：0，high：6
2. 开始循环：我们进入一个循环，直到 mid 小于或等于 high。
3. 检查 mid 处的值：我们检查 mid 指向位置的值，在本例中为 0。
4. 值为 0：由于值为 0，我们交换 low 和 mid 位置的元素，将 0 移到开头。
   • 交换后的数组：[0, 1, 2, 1, 0, 2, 1]
   • low：1，mid：1，high：6
5. 递增 low 和 mid：交换后，我们同时递增 low 和 mid 指针。
   • 数组：[0, 0, 2, 1, 1, 2, 1]
   • low：1，mid：2，high：6
6. 继续循环：我们继续循环，因为 mid 仍小于 high。
7. 检查 mid 处的值：我们检查 mid 处的值，现在是 2。
8. 值为 2：由于值为 2，我们交换 mid 和 high 位置的元素，将 2 移到末尾。
   • 交换后的数组：[0, 0, 1, 1, 1, 2, 2]
   • low：1，mid：2，high：5
9. 递减 high：交换后，我们递减 high。
   • 数组：[0, 0, 1, 1, 1, 2, 2]
   • low：1，mid：2，high：4
10. 继续循环：我们再次继续循环。
11. 检查 mid 处的值：mid 处的值现在是 1。
12. 值为 1：由于值为 1，我们递增 mid 以将 1 保持在中间。
    • 数组：[0, 0, 1, 1, 1, 2, 2]
    • low：1，mid：3，high：4
13. 继续循环：我们继续循环。
14. 检查 mid 处的值：mid 处的值仍然是 1。
15. 值为 1：我们递增 mid。
    • 数组：[0, 0, 1, 1, 1, 2, 2]
    • low：1，mid：4，high：4
16. 结束循环：现在，mid 等于 high，因此我们退出循环。
17. 结果：数组现已按要求排序：[0, 0, 1, 1, 1, 2, 2]。

大功告成！荷兰国旗算法已有效地对数组进行了排序，就像排列荷兰国旗中的颜色一样——0、1 和 2 按完美的顺序排列。

方法一：双指针法

输出

0 0 0 0 0 1 1 1 1 1 2 2

说明

1. 函数定义
   • 程序首先定义了两个函数：
     • sort_array_012(arr, size)：此函数接受数组 arr 和其大小 size 作为输入，并以特定方式对其进行排序。
     • print_sorted_array(arr)：此函数打印已排序的数组 arr。
2. 初始化
   • 在 sort_array_012 函数内部，初始化了三个变量：low、high 和 mid。这些变量用于在排序过程中跟踪数组中的位置。
   • low 设置为 0，high 设置为 size - 1，mid 设置为 0。
3. 排序循环
   • 使用 while 循环迭代数组，直到 mid 小于或等于 high。
4. 排序逻辑
   • 在循环中，程序会检查 mid 位置的元素的值。
     • 如果元素是 0，它会交换 low 和 mid 位置的元素，将 0 有效地移到数组的开头。然后，它同时递增 low 和 mid。
     • 如果元素是 1，它只需递增 mid 以移至下一个元素。
     • 如果元素是 2，它会交换 mid 和 high 位置的元素，将 2 移到数组的末尾。然后，它递减 high。
5. 返回已排序数组
   • 循环完成后，sort_array_012 函数返回已排序的数组 arr。
6. 打印已排序数组
   • 在 print_sorted_array 函数中，使用 for 循环迭代已排序的数组，并打印每个元素，元素之间用空格分隔。
7. 驱动代码
   • 最后，函数外部的驱动代码定义了一个包含 0、1 和 2 的输入数组 input_array。
   • 使用 len(input_array) 确定数组的大小。
   • 调用 sort_array_012 函数对输入数组进行排序，并将排序结果存储在 sorted_array 中。
   • 调用 print_sorted_array 函数将已排序的数组打印到控制台。
8. 输出
   • 运行程序时，它会在一次遍历中对输入数组进行排序，并根据荷兰国旗问题打印已排序的数组。

方法二：计数法

方法解释

1. 计数频率
   • 在此方法中，程序首先计算输入数组中 0、1 和 2 的频率。
   • 使用三个变量 cnt0、cnt1 和 cnt2 来跟踪 0、1 和 2 的计数。
2. 计数循环
   • 程序遍历整个输入数组。
   • 对于遇到的每个元素，它会检查其值并递增相应的计数变量。
3. 更新数组
   • 计算频率后，程序会更新输入数组。
   • 它首先根据 0 的计数 (cnt0) 用 0 填充数组。
   • 然后，它根据 1 的计数 (cnt1) 用 1 填充数组。
   • 最后，它根据 2 的计数 (cnt2) 用 2 填充数组的其余部分。
4. 打印已排序数组
   • 程序包含一个实用函数 printArr 来打印数组的内容。
   • 更新数组后，它调用 printArr 来打印已排序的数组。
5. 驱动代码
   • 驱动代码初始化输入数组 arr 及其长度 n。
   • 然后，它调用 sortArr 函数，使用计数法根据荷兰国旗问题对数组进行排序。

输出

0 0 0 0 0 1 1 1 1 1 2 2

说明

1. 打印实用函数
   • 程序首先定义了一个名为 printArr 的实用函数。此函数负责打印数组的内容。它接受两个参数：arr（要打印的数组）和 n（数组的长度）。
2. 排序函数
   • 核心排序逻辑实现在 sortArr 函数中，该函数在修改后的代码中被重命名为 dutch_flag_sort_counting。
3. 计数变量
   • 在排序函数内部，初始化了三个变量 count_0、count_1 和 count_2，以跟踪输入数组中 0、1 和 2 的计数。
4. 计数循环
   • 程序进入一个循环，该循环遍历整个输入数组。
   • 对于遇到的每个元素，它会检查其值，并根据元素是 0、1 还是 2 来递增相应的计数变量（count_0、count_1 或 count_2）。
5. 更新数组
   • 在计算完 0、1 和 2 的频率后，程序继续更新输入数组以对其进行排序。
   • 它首先根据 0 的计数 (count_0) 用 0 填充数组。它通过在递减 count_0 和前进索引 i 的同时，从数组开头反复将元素设置为 0 来实现此目的。
   • 同样，它根据 1 的计数 (count_1) 用 1 填充数组。
   • 最后，它根据 2 的计数 (count_2) 用 2 填充数组的其余部分。
6. 打印已排序数组
   • 更新数组后，程序调用 print_sorted_array 函数将已排序的数组打印到控制台。此函数遍历数组并打印每个元素，元素之间用空格分隔。
7. 驱动代码
   • 程序底部的驱动代码初始化了一个包含 0、1 和 2 的输入数组 input_array。
   • 它使用 len(input_array) 计算数组的长度，以确定数组的大小。
   • 最后，它调用 dutch_flag_sort_counting 函数，使用计数法根据荷兰国旗问题对输入数组进行排序。