1. 简介
在本文中，我们将介绍如何对一个数值数组进行重排，使得其中的负数元素全部出现在正数元素之前（包括零）。同时，我们要求保持原数组中同符号元素的相对顺序不变。
2. 问题描述
给定一个数组 a = [a₁, a₂, ..., aₙ]，我们的目标是将其重排为 a' = [a₁', a₂', ..., aₖ', aₖ₊₁', ..., aₙ']，满足：
- 所有
aⱼ'（j ≤ k）为负数； - 所有
aⱼ'（j > k）为非负数（包括零）； - 同符号元素的相对顺序与原数组一致。
例如，输入数组为：
a = [10, -2, 30, -4, 1, -20, 3, -40]
期望输出为：
a' = [-2, -4, -20, -40, 10, 30, 1, 3]
3. 使用两个队列的解法
我们可以使用两个队列来分别保存负数和非负数。遍历数组时，根据元素的符号分别入队。最后将两个队列拼接，即可得到结果。
✅ 优点
- 时间复杂度：O(n)
- 空间复杂度：O(n)
✅ 实现伪代码
algorithm SolutionWithQueues(a):
queue_negative = new Queue()
queue_positive = new Queue()
for i from 0 to length(a) - 1:
if a[i] < 0:
queue_negative.enqueue(a[i])
else:
queue_positive.enqueue(a[i])
result = queue_negative.concatenate(queue_positive)
return result
⚠️ 注意
虽然实现简单，但需要额外的 O(n) 空间，适用于对空间不敏感的场景。
4. 原地合并解法（类似 MergeSort）
如果我们希望减少空间使用，可以采用一种类似 MergeSort 的方法，称为 MergeArrange。
✅ 核心思想
- 将数组划分为子数组；
- 每次合并相邻子数组，并调整内部顺序；
- 最终将整个数组调整为负数在前、正数在后，同时保持相对顺序。
✅ 时间与空间复杂度
- 时间复杂度：O(n log n)
- 额外空间复杂度：**O(1)**（原地操作）
✅ 合并两个子数组的步骤
假设我们有两个子数组：
[L_- L_+] [R_- R_+]
我们需要将 L_+ 与 R_- 交换位置，并保持它们各自的顺序。具体操作如下：
- 反转
L_+ - 反转
R_- - 再次整体反转这两个子数组拼接后的部分
✅ 示例
以数组 [10, -2, 30, -4, 1, -20, 3, -40] 为例：
- 初始分割为
[10] [-2] [30] [-4] [1] [-20] [3] [-40] - 第一次合并后变为
[-2, 10] [-4, 30] [-20, 1] [-40, 3] - 第二次合并后变为
[-2, -4, 10, 30] [-20, -40, 1, 3] - 第三次合并后变为最终结果：
[-2, -4, -20, -40, 10, 30, 1, 3]
✅ 伪代码
algorithm MergeArrange(a):
n = length(a)
l = 1
m = ceiling(n / 2)
while m > 1:
for i from 0 to n - 1 step 2 * l:
Reverse(a, i, i + l - 1)
Reverse(a, i + l, i + 2 * l - 1)
Reverse(a, i, i + 2 * l - 1)
l = 2 * l
m = ceiling(n / l)
return a
algorithm Reverse(a, i, j):
while i < j:
swap a[i], a[j]
i += 1
j -= 1
⚠️ 注意
- 该算法适用于对空间敏感但允许稍高时间复杂度的场景；
- 逻辑较复杂，需要仔细处理边界条件；
- 是一种稳定的重排算法。
5. 总结
我们介绍了两种将数组中负数元素排在正数元素之前的解法：
| 方法 | 时间复杂度 | 空间复杂度 | 是否稳定 | 适用场景 |
|---|---|---|---|---|
| 双队列 | O(n) | O(n) | ✅ 是 | 空间允许时 |
| 原地合并（MergeArrange） | O(n log n) | O(1) | ✅ 是 | 空间受限时 |
两种方法各有优劣，可根据具体场景选择合适的实现方式。如果你追求速度，双队列法是更优选择；如果内存受限，原地合并法更合适。