在排列数组中的所有负数和正数时，如何避免交换负数

Question

这就是我正在研究的问题：

给定一个由N个正数和负数组成的未排序数组Arr。您的任务是在不更改正数和负数的相对顺序的情况下创建一个正数和负数数组。

所以，这是我天真的想法！我使用插入排序的变体。

这是代码：

void reorder(int arr[], int n) {
for (int i = 0; i < n; i++) {
int hole = i;
while ((arr[hole] < 0) && (hole > 0)) {
int temp = arr[hole];
arr[hole] = arr[hole - 1];
arr[hole - 1] = temp;
hole--;
} 
}
}

此代码更改负数的相对位置，这是不需要的。如何避免在代码中出现这种情况？

示例

输入：

arr = { -12, 11, -13, -5, 6, -7, 5, -3, -6 };

预期结果：

-12 -13 -5 -7 -3 -6 11 6 5 

但我的结果是：

-6 -3 -7 -5 -13 -12 11 6 5

Answer 1

请注意，赋值为"您的任务是创建一个数组">。。。因此，如果我理解正确，您不会被要求修改输入数组，而是创建一个。

因此，解决方案相当琐碎：

• 创建与输入数组大小相同的数组
• 迭代输入数组并将负值复制到新数组中
• 再次迭代输入数组，现在将正值复制到新数组中
• 返回新数组

这具有线性时间复杂性。