编写 Python 程序对 0、1 和 2 的列表进行排序

在本教程中，我们编写了排序 0、1 和 2 列表的程序。这里的 0、1 和 2 列表是指列表只包含 0、1 和 2 形式的数据。例如，一个包含 11 个元素的数组，这些元素如下：0、1、1、2、2、1、0、2、1、0、0。

问题陈述

问题是给定一个大小为 N 的数组，其中只包含 0、1 和 2；请将数组按升序排序。例如：

示例 - 1

示例 - 2

解决方案

我们将使用以下方法来解决这个问题。

• 暴力破解法
• 荷兰国旗算法

让我们来理解一下暴力破解法。

方法 - 1

要使用暴力破解法解决这个问题，我们将使用冒泡排序算法。让我们来理解下面的代码片段。

示例 -

输出

The Given Array is: [2, 0, 2, 1, 1, 0]
The Sorted Array is: [0, 0, 1, 1, 2, 2]

解释 -

在上面的代码中，我们定义了一个 sort_array() 函数，它接受一个输入数组 "arr" 作为参数，并返回一个排序后的输入数组版本。

该函数使用冒泡排序算法对数组进行排序。该算法的基本思想是重复比较数组中的相邻元素，如果它们的顺序错误，则交换它们。重复此过程，直到整个数组排序完毕。

该函数首先使用内置的 "len" 函数确定输入数组的长度，并将其赋值给变量 "n"。然后，它使用两个 "for" 循环进入嵌套循环结构，以迭代数组中的每个元素。外层循环迭代从第一个元素到最后一个元素的每个数组元素，而内层循环迭代从第一个元素到最后一个未排序元素的每个元素。

在嵌套循环中，函数使用 "if" 语句比较数组中的相邻元素，以检查左边的元素是否大于右边的元素。如果此条件为真，则使用元组赋值语句交换这两个元素。

arr[j], arr[j + 1] = arr[j + 1], arr[j] 语句是交换 arr[j] 和 arr[j+1] 值的简写方式。它会创建一个包含要交换的两个值的临时元组，然后解包该元组并将值分配给各自的变量。

嵌套循环完成后，函数使用 "return" 语句返回已排序的输入数组。最终输出将是相同的数组，但其元素已按升序排序。

方法 - 2

为了排序 0、1 和 2，我们将使用 **荷兰国旗算法**，这是一个相当高效的算法，用于处理具有不同元素的数组。让我们来理解下面的示例。

示例 -

输出

The Given Array is: [2, 0, 2, 1, 1, 0]
The Sorted Array is: [0, 0, 1, 1, 2, 2]

解释 -

在上面的代码中，我们定义了 sort_arr() 函数，它接收一个 0、1 和 2 的列表并返回排序后的列表。首先，我们初始化三个指针 "low"、"mid" 和 "high"，它们用于跟踪数组中 0、1 和 2 的位置。

while 循环一直持续到 "mid" 指针到达数组末尾。在循环中，我们需要考虑三种情况：

• 如果 "mid" 位置的元素是 0，我们将其与 "low" 位置的元素交换，然后同时增加 "low" 和 "mid"。
• 如果 "mid" 位置的元素是 1，我们无需执行任何操作，只需将 "mid" 加一。
• 如果 "mid" 位置的元素是 2，我们将其与 "high" 位置的元素交换，然后将 "high" 减一。

循环结束后，数组将按升序排序，所有 0 都在前面，然后是所有 1，最后是所有 2。我们使用 "return" 语句返回排序后的数组。

该算法的时间复杂度为 O(n)，其中 n 是输入数组的长度，空间复杂度为 O(1)，因为它在原地排序数组，不使用任何额外空间。

结论

在本教程中，我们通过两种方法解决了 0、1 和 2 列表的排序问题——第一种方法我们使用了时间复杂度为 0(N²) 的冒泡排序算法。在第二种方法中，我们实现了 **荷兰国旗算法**，它比冒泡排序更有效，因为其时间复杂度为 0(N)。