C++实现数组分区重排：小于3元素置左、大于3元素置右

现有代码存在的核心问题 #

• 计数器c未做初始化，且满足元素判断条件时没有自增操作，会导致收集元素时反复覆盖临时数组的同一个位置，无法按顺序留存小于3的元素
• 仅实现了小于3的元素收集分支，完全遗漏了大于3的元素收集逻辑，无法凑齐完整长度的重排数组
• 缺少将收集完成的重排元素回写目标数组、输出最终结果的步骤

方案一：补全原有临时数组收集逻辑（和你现有代码思路完全匹配） #

核心实现逻辑：

1. 第一遍遍历原数组，按原始顺序将所有小于3的元素存入临时数组，每存入一个元素计数器后移一位
2. 保持当前计数器位置，第二遍遍历原数组，按原始顺序将所有大于3的元素接在临时数组的左侧元素后面
3. 将临时数组的有效元素批量覆盖回原数组，完成分区重排

完整可运行示例代码：

#include <iostream>
using namespace std;

int main() {
    // 给定测试数组
    const int n = 10;
    int arr[n] = {10, 64, 79, 6, 13, -14, 1, 0, 66, 2};
    int indexes[1000];
    int c = 0; // 初始化计数器从0开始，补全原有代码的缺失逻辑

    // 第一遍：收集小于3的元素放在临时数组左侧
    for(int i = 0; i < n; i++) {
        if(arr[i] < 3) {
            indexes[c] = arr[i];
            c++; // 每存一个元素，计数器后移
        }
    }

    // 第二遍：收集大于3的元素接在临时数组的左侧元素后方
    for(int i = 0; i < n; i++) {
        if(arr[i] > 3) {
            indexes[c] = arr[i];
            c++;
        }
    }

    // 将重排结果写回原数组
    for(int i = 0; i < n; i++) {
        arr[i] = indexes[i];
    }

    // 打印输出，可得到目标结果：-14 1 0 2 10 64 79 6 13 66
    for(int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    return 0;
}

方案二：原地双指针交换（无需大尺寸临时数组，空间效率更高） #

如果不希望开辟1000长度的临时数组，可以用双指针在原数组上直接完成分区，不需要额外开辟大尺寸存储空间：

#include <iostream>
#include <utility> // 提供swap方法
using namespace std;

void partition(int arr[], int n) {
    int left = 0;
    int right = n - 1;
    while(left < right) {
        // 左指针跳过所有小于3的元素，找到第一个需要交换的位置
        while(left < right && arr[left] < 3) left++;
        // 右指针跳过所有大于3的元素，找到第一个需要交换的位置
        while(left < right && arr[right] > 3) right--;
        // 交换两个错位的元素
        if(left < right) {
            swap(arr[left], arr[right]);
            left++;
            right--;
        }
    }
}

int main() {
    const int n = 10;
    int arr[n] = {10, 64, 79, 6, 13, -14, 1, 0, 66, 2};
    partition(arr, n);
    // 输出结果和方案一完全一致
    for(int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    return 0;
}

内容的提问来源于stack exchange，提问作者Happy Wheels