C++实现计数排序时如何跳过count数组累加步骤直接得到排序结果

实现逻辑 #

你要求的优化可通过利用计数数组下标天然对应待排序元素值的特性实现，不需要前缀和计算就能直接生成有序数组，具体调整如下：

• 保留原版代码中求数组最大值、初始化计数数组、统计元素出现频次的逻辑
• 删除原有的前缀和累加循环、反向遍历原数组填充输出数组的两段逻辑
• 新增写入指针控制输出数组填充位置：从小到大遍历计数数组下标，每个下标对应的值有多少个，就往输出数组里连续写入多少次当前下标值

*注意：该版本不保留排序稳定性，若你需要排序后相同值的元素相对顺序和原数组一致，仍需使用带前缀累加的原版实现；纯整数排序场景下该版本逻辑更简洁，执行效率更高。 #

核心修改代码段 #

统计完频次后，将原有前缀和、填充逻辑替换为以下代码即可：

int write_pos = 0;
// 从小到大遍历计数数组下标，直接填充有序数组
for(int i = 0; i <= max; i++) {
    while(count[i]--) {
        output[write_pos++] = i;
    }
}

完整可运行代码 #

#include<iostream>
using namespace std;

int getMx(int* arr,int n)
{
    int max = arr[0];
    for (int i = 1; i < n; i++)
    {
        if (arr[i] > max)
        {
            max = arr[i];
        }       
    }
    return max;
}

void CountSort(int* arr, int n) {
    int* output = new int[n];
    int max = getMx(arr, n);
    int* count = new int[max + 1];

    for(int i = 0; i < max + 1; i++) {
        count[i] = 0;
    }

    // 统计元素出现频次
    for(int i = 0; i < n; i++) {
        count[arr[i]]++;
    }

    // 优化后逻辑：无前置累加直接填充有序数组
    int write_pos = 0;
    for(int i = 0; i <= max; i++) {
        while(count[i]--) {
            output[write_pos++] = i;
        }
    }

    // 有序数组拷贝回原数组
    for(int i = 0; i < n; i++) {
        arr[i] = output[i];
    }

    delete[] output;
    delete[] count;
}

int main () {
    // 测试用例1：原示例数组
    int arr[] = { 100, 5, 2, 0, 125 };
    int n = sizeof(arr) / sizeof(arr[0]);
    CountSort(arr, n);
    cout << "测试用例1输出：" << endl;
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    // 测试用例2：你给出的示例数组
    int arr2[] = {3, 2, 5, 4, 1, 0};
    int n2 = sizeof(arr2)/sizeof(arr2[0]);
    CountSort(arr2, n2);
    cout << "测试用例2输出：" << endl;
    for (int i = 0; i < n2; i++) {
        cout << arr2[i] << " ";
    }
    return 0;
}

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