在 C++ 中用恒定的额外空间重新排列正数和负数

我们得到一个包含正数和负数的整数类型数组，比方说，任何给定大小的 arr[] 。任务是以这样一种方式重新排列数组，即使用 C++ STL 的内置排序函数以及使用编码和打印结果的递归技术对数组的所有元素进行排序。

让我们看看这个的各种输入输出场景 -

输入 - int arr[] = {4, 2, -1, -1, 6, -3, 0}

输出 - 具有恒定额外空间的正负数的重新排列是：-3 -1 -1 0 6 2 4。

说明 - 我们得到一个大小为 7 的整数数组，其中包含正元素和负元素。现在，我们将重新排列数组，使数组的所有元素都在常量额外空间内排序，最终结果将为 -3 -1 -1 0 2 4 6。

输入 - int arr[] = {-9, -10, 2, 3, 10, 5, 8, 4}

输出 - 具有恒定额外空间的正负数的重新排列是：-9 -10 2 3 10 5 8 4

说明- 我们得到一个大小为 8 的整数数组，其中包含正元素和负元素。现在，我们将重新排列数组，使数组的所有元素都在常量额外空间内排序，最终结果将是 -9 -10 2 3 10 5 8 4。

下面程序中使用的方法如下

• 输入整数类型元素的数组并计算数组的大小。

• 在使用 FOR 循环执行重新排列操作之前打印一个数组。

• Rearrangement(arr, size)通过传递数组和数组大小作为参数来调用该函数。

• 函数内部 Rearrangement(arr, size)

• 将整数类型变量声明为 i 到 0 和 j 到大小 -1。

• 开始while(true)。在 while 中，当 arr[i] 小于 0 且 i 小于 size 时开始另一个循环，然后将 i 增加 1。

• 开始 WHILE arr[j] 大于 0 且 j 大于 0 然后将 j 减 1。

• 检查如果 i 小于 j 然后将 temp 设置为 arr[i]，将 arr[i] 设置为 arr[j] 并将 arr[j] 设置为 temp。

• 否则，休息。

• 打印结果。

示例

#include<iostream>
using namespace std;
void Rearrangement(int arr[], int size){
   int i = 0;
   int j = size - 1;
   while(true){
      while(arr[i] < 0 && i < size){
         i++;
      }
      while(arr[j] > 0 && j >= 0){
         j--;
      }
      if (i < j){
         int temp = arr[i];
         arr[i] = arr[j];
         arr[j] = temp;
      }
      else{
         break;
      }
   }
}
int main(){
   int arr[] = {4, 2, -1, -1, 6, -3, 0};
   int size = sizeof(arr)/sizeof(arr[0]);
   //调用函数重新排列数组
   Rearrangement(arr, size);
   //重新排列值后打印数组
   cout<<"具有恒定额外空间的正数和负数的重新排列是： ";
   for(int i = 0; i < size; i++){
      cout<< arr[i] << " ";
   }
   return 0;
}

如果我们运行上面的代码，它将生成以下输出

具有恒定额外空间的正数和负数的重新排列是： -3 -1 -1 0 6 2 4