C++数组排序求助：正/零升序、负数降序后合并至数组B

嘿，我看你已经完成了核心的排序工作，就差最后一步把两部分合并到数组B里了！咱们先梳理下现有代码的小问题，再给出完整的解决方案。

现有代码的核心问题 #

你已经把非负数升序、负数降序处理好了，但在合并时犯了两个小错误：

1. 往B数组存非负数时，用了原数组的索引i，导致B数组出现空位（原数组负数对应的位置没被赋值）；
2. 收集好负数到A_negative后，没有把这些元素放到B数组的后半段。

另外，你的代码里两次排序整个数组其实可以优化——第一次排序后，原数组已经是整体升序，此时负数在数组前半段（升序），非负数在数组后半段（升序），咱们直接利用这个结果就能得到负数降序，不用再排序一次。

修改后的完整代码 #

下面是优化后的代码，我会逐段解释：

#include <iostream>
#include <cstring>
using namespace std;

int main() {
    int i, j, n, A[100], B[100], aux, k = 0;
    
    cout << "请输入数组元素个数：";
    cin >> n;
    cout << "请输入数组元素：" << endl;
    for(i = 0; i < n; i++) {
        cin >> A[i];
    }

    // 第一步：对整个数组进行升序排序
    for(i = 0; i < n; i++)
        for(j = i + 1; j < n; j++)
            if(A[i] > A[j]) {
                aux = A[i];
                A[i] = A[j];
                A[j] = aux;
            }

    // 第二步：把升序的非负数先存入B数组（此时非负数在原数组后半段，已经是升序）
    for(i = 0; i < n; i++){
        if(A[i] >= 0){
            B[k] = A[i];
            k++; // k记录非负数的个数，同时作为B数组的下一个赋值位置
        }
    }

    // 第三步：把负数按降序存入B数组的后半段
    // 原数组升序后负数是升序的，从后往前遍历负数部分就能得到降序
    for(i = n - 1; i >= 0; i--){
        if(A[i] < 0){
            B[k] = A[i];
            k++;
        }
    }

    // 输出最终结果
    cout << "排序后的数组B：" << endl;
    for(i = 0; i < n; i++){
        cout << B[i] << " ";
    }
    cout << endl;

    return 0;
}

代码解释 #

1. 整体升序排序：排序后你的示例数组会变成{-8,-7,-6,0,4,5,7}，负数在前（升序），非负数在后（升序），完美符合咱们的基础需求；
2. 存入非负数：遍历原数组，把所有>=0的元素依次放到B数组的前半段，用k跟踪当前赋值的位置，最后k的值就是非负数的总数；
3. 存入降序负数：因为原数组的负数是升序的，咱们从数组末尾往前找负数，依次放到B数组的k位置之后，这样就自然得到了降序的负数；
4. 输出结果：最后遍历B数组，就能得到你想要的{0,4,5,7,-6,-7,-8}。

如果你坚持要用原来的A_nenegative和A_negative数组分开存储的方式，也可以这样修改：

// 原代码中第一次排序后修改这部分：
k = 0;
for(i = 0; i< n; i++)
    if(A[i]>=0) {
        A_nenegative[k] = A[i]; // 用k作为A_nenegative的索引，避免空位
        k++;
    }
// 把A_nenegative的元素放到B的前k位
for(i = 0; i < k; i++){
    B[i] = A_nenegative[i];
}

// 第二次排序后修改：
m = 0;
for(i=0;i<n;i++)
    if(A[i]<0) {
        A_negative[m] = A[i]; // 用m作为A_negative的索引
        m++;
    }
// 把A_negative的元素放到B的k位之后
for(i = 0; i < m; i++){
    B[k + i] = A_negative[i];
}

不过这种方式需要额外的两个数组，不如前面的优化方案高效。

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