C 语言将所有负数移到数组的一侧

数组是同质的。整数数组可以容纳负值、正值或零。我们需要重新排列数组的元素，使所有负元素都移到数组的一侧，要么在开头，要么在末尾。这里元素的顺序并不重要。

这是最常被问到的面试问题之一，并且有很多方法可以解决它。本教程列出了所有可能的方法及示例。

例如，如果我们给出一个数组

结果数组可以是

1. 负元素移到数组开头
   
2. 负元素移到数组末尾
   

注意：顺序不必考虑。关键是将所有负数移到一侧。

听到这个问题时，首先想到的方法是朴素的方法——对数组进行排序。

如果我们按升序对数组进行排序，所有负元素都会堆积在数组的开头，如果我们按降序排序，所有元素都会堆积在末尾。

我们可以使用任何排序算法来执行排序。我们以选择排序为例

在选择排序算法中，对于数组中的每个元素 i，我们将在 i+1 到数组末尾的子数组中找到最小元素，然后交换这两个值来对数组进行排序。

代码

输出

Enter the size of the Array: 5
Enter the elements: 5 -8 3 -9 2
The final Array: -9 -8 2 3 5

如果我们采用这种方法，时间复杂度为 O(n²)，其中 n 是数组的长度。

现在，让我们关注更有效的方法。

我们在上面的方法中使用了嵌套的 for 循环，这增加了时间复杂度。我们需要一种方法来在一遍遍历数组的情况下完成过程。

1. 使用分区方法

在此方法中，我们遍历数组，一旦找到负数，就将其放在数组的开头或末尾。

代码

输出

Enter the size of the Array: 6
Enter the elements: 1-3 2 -5 -6 -1
The resultant Array: -3 -5 -6 -1 2 1

理解

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

例如

假设给定的数组是

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

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

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

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

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

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

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

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

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

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

2. 使用指针/变量

在此方法中，我们使用两个指针或变量，例如，a 指向数组的开头，b 指向数组的末尾。我们将通过递增 a 和递减 b 来检查数组中的元素。

将所有负值移到开头，所有正值移到末尾

算法

1. 如果 a 和 b 都指向负数，则递增 a。
2. 如果 a 指向正数而 b 指向负数，则交换 a 和 b 的值。
3. 如果 a 和 b 都指向正数，则递减 b。
4. 如果 a 指向负数而 b 指向正数，则递增 a 并递减 b。

代码

输出

Enter the size of the Array: 6
Enter the elements: 1 -3 4 -2 4 -3
The resultant Array: -3 -3 -2 4 4 1

3. 荷兰国旗算法

由 Dijkstra 提出，给定 n 个红、白、蓝球以随机顺序排列，我们需要将所有球排列起来，使相同颜色的球都相邻。这些球组的顺序必须是给定的顺序，也就是说，在所有红球之后是白球，然后是蓝球。

我们像上面方法一样从两边缩小数组。这段代码就像上面方法的简化版。

代码

输出

Enter the size of the Array: 6
Enter the elements: 4 -2 4 -1 -2 -5
The resultant Array: -5 -2 -2 -1 4 4

理解

注意，在上面的代码中，我们使用了与前一种方法相同的条件，但对其进行了进一步简化。