自定义comp函数实现数组正负分区失败，求正确原地重排方案

需求 #

给定大小为N的数组，原地重排数组，使所有负数位于非负数之前，且保持负数和非负数在原数组中的相对顺序。

示例 #

• 输入：N = 4，Arr[] = {-3, 1, 0, -2}
• 输出：-3 -2 1 0

我的实现 #

需要完成Rearrange()函数，我编写的代码如下：

static bool comp(int a, int b) { return (a < 0 && b >= 0); }

void Rearrange(int arr[], int n) { sort(arr, arr + n, comp); }

该代码在测试用例10时失败，测试用例详情：

数组大小：91
数组元素：263 22 270 343 -101 -398 -154 193 157 168 -166 292 142 -104 310 294 1 -449 223 -216 -33 394 -197 233 329 -439 -423 -317 443 -174 241 288 167 117 -360 -12 86 -62 109 -15 267 76 296 388 -132 -342 400 240 -46 -163 436 288 434 384 -351 305 -199 -158 427 169 288 -406 305 295 264 129 423 -2 -261 -46 -200 -1 453 404 351 420 68 -433 -82 -131 -71 -66 -42 333 17 34 -393 -262 54 342 -53

代码失败原因 #

1. 比较器违反严格弱序规则：C++标准库sort要求比较函数必须满足严格弱序。你的comp(a,b)仅在a为负数且b为非负数时返回true，其余情况（两个负数、两个非负数）都返回false，这会让sort无法正确判断元素的相对优先级，导致排序结果完全不符合预期。
2. 默认sort是不稳定排序：即便比较器合法，sort也会打乱同类别元素（比如两个负数）的原始顺序，无法满足题目“保持相对顺序”的要求。

正确解法 #

方法1：稳定排序法（简单高效） #

使用stable_sort搭配合法的比较器，既能保证负数在前，又能保留同类别元素的原始顺序：

bool comp(int a, int b) {
    // 负数优先于非负数；同类别元素由stable_sort保证顺序
    if (a < 0 && b >= 0) return true;
    if (a >= 0 && b < 0) return false;
    return false;
}

void Rearrange(int arr[], int n) {
    stable_sort(arr, arr + n, comp);
}

方法2：原地插入法（O(1)额外空间） #

遍历数组，遇到负数时将其逐步交换到已处理负数的末尾位置，完全原地操作且严格保持相对顺序：

void Rearrange(int arr[], int n) {
    int neg_pos = 0; // 标记下一个负数的目标位置
    for (int i = 0; i < n; ++i) {
        if (arr[i] < 0) {
            // 从当前位置交换到neg_pos
            for (int j = i; j > neg_pos; --j) {
                swap(arr[j], arr[j-1]);
            }
            neg_pos++;
        }
    }
}

方法3：辅助数组法（实现简单，空间O(n)） #

如果允许使用额外空间，先分别收集负数和非负数，再复制回原数组：

#include <vector>

void Rearrange(int arr[], int n) {
    std::vector<int> temp;
    // 先收集所有负数
    for (int i = 0; i < n; ++i) {
        if (arr[i] < 0) temp.push_back(arr[i]);
    }
    // 再收集所有非负数
    for (int i = 0; i < n; ++i) {
        if (arr[i] >= 0) temp.push_back(arr[i]);
    }
    // 覆盖原数组
    for (int i = 0; i < n; ++i) {
        arr[i] = temp[i];
    }
}

内容的提问来源于stack exchange，提问作者s p