分割数组中的 0 和 1

给定一个只有0和1随机排列的数组，任务是将所有0和1分开。我们可以将所有0排在前面，然后是1，或者将所有1排在前面，然后是0。本教程列出了从朴素方法到高效方法的所有可能方法来分离0和1的数组。

方法1：朴素方法：排序数组

如果我们将数组按升序排序，我们会得到一个0在前，1在后的数组。对于1在前，0在后的数组，我们需要将数组按降序排序。

下面是一个遵循选择排序算法的示例代码

输出

Enter the size of the Array: 6
Enter the elements: 0 1 1 1 0 0
0 0 0 1 1 1

我们在这里使用了两个循环，一个用于选择数组中的元素，另一个用于查找数组中的最小元素。因此，时间复杂度为O(N²)。

方法2：两次遍历数组：计数

在此方法中，我们将只遍历数组两次以降低时间复杂度。但我们该怎么做呢？我们将使用第一次遍历来计算数组中0的个数。通过从数组大小中减去0的个数，我们将得到1的个数。现在，我们将使用第二次遍历用0填充数组，然后是1。

示例代码

输出

Enter the size of the Array: 6
Enter the elements: 0 1 1 0 1 1
The resultant Array: 0 0 1 1 1 1

方法3：只遍历一次数组：双指针/变量

在此方法中，我们使用两个变量或指针，一个从数组的开头开始，另一个从数组的末尾开始。如果我们正将0排在前面，然后是1，我们将使用两个变量检查右侧是否有0，左侧是否有1，并交换它们。

输出

Enter the size of the Array: 6
Enter the elements: 1 1 1 0 0 0
The resultant Array: 0 0 0 1 1 1

理解

在上面的代码中，我们有两个变量a和b，分别指向数组的开头和结尾。

这里的逻辑是，

1. 如果我们发现数组的右侧有一个0，左侧有一个1，我们将交换这两个元素。
2. 如果我们发现右侧有一个0，左侧也有一个0，我们就不能交换它们，因为左侧的0不应被移动。因此，我们将增加起始变量到下一个位置，直到我们找到一个1来与右侧的0交换。
3. 对于数组左侧的1，如果没有右侧的0，机制也是一样的。我们将递减右侧变量到前一个位置，以找到一个0来与左侧的1交换。

方法4：只遍历一次数组：分区方法

在此方法中，我们使用两个变量，就像上面的方法一样，但都从数组的开头开始。我们将使用一个变量（i）来遍历数组以查找0，使用变量（j）指向数组的开头。如果i找到一个0，我们将交换i和j处的元素，然后我们将增加j。为了说清楚，j是我们希望0占据的索引。

示例代码

输出

Enter the size of the Array: 6
Enter the elements: 1 1 0 0 1 1
The resultant Array: 0 0 1 1 1 1

理解

在上面的代码中，我们声明了一个变量j=0，arr[j]位于数组的开头。现在，我们使用i遍历数组，在每次迭代中，我们检查arr[i]是否为0。如果arr[i]为0，我们将其与arr[j]交换，以将其移到数组的开头。然后，我们增加j的值并继续该过程。

例如

第一次迭代 -> j = 0, i = 0 -> arr[0]是1

第二次迭代 -> j = 0, i = 1 -> arr[1]是0，且i != j

所以交换 arr[0] <-> arr[1]

j = j + 1

第三次迭代 -> j = 1, i = 2 -> arr[2]是1

第四次迭代 -> j = 1, i = 3 -> arr[3]是0，且i != j

所以交换 arr[1] <-> arr[3]

第五次迭代 -> j = 2, i = 4 -> arr[4]是0，且i != j

所以交换 arr[2] <-> arr[4]

第六次迭代 -> j = 3, i = 5 -> arr[5]是0，且i != j，所以交换 arr[3] <-> arr[5]

时间复杂度：O(n)，其中n是数组的大小