编辑代码

#include <iostream>
using namespace std;

//线性计数排序的C++实现
void CountSort(int* arr, int size) {
    //找出数组中的最大值和最小值
    int max = arr[0];
    int min = arr[0];
    for (int i = 1; i < size; i++) {
        if (arr[i] > max) 
            max = arr[i];
        if (arr[i] < min) 
            min = arr[i];
        
    }
    //计算数据范围
    int range = max - min + 1;
    //创建一个计数数组，用于存储每个元素出现的次数
    int* count = new int[range];
    //初始化计数数组为0
    for (int i = 0; i < range; i++)
        count[i] = 0;

    //遍历原数组，统计每个元素出现的次数
    for (int i = 0; i < size; i++)
        count[arr[i] - min]++;
    //遍历计数数组，将元素按照顺序放回原数组
    int index = 0; //用于记录原数组的下标
    for (int i = 0; i < range; i++) {
        //如果计数数组中的元素不为0，说明有对应的元素
        while (count[i] > 0) {
            //将元素放回原数组，注意要加上最小值的偏移量
            arr[index] = i + min;
            //更新原数组的下标
            index++;
            //更新计数数组中的元素，减少一个
            count[i]--;
        }
    }
    //释放计数数组的内存空间
    delete[] count;
}

//main函数，用于测试线性计数排序
int main() {
    //创建一个测试数组
    int arr[] = {5, 3, 7, 2, 9, 1, 4, 6, 8};
    //获取数组的长度
    int size = sizeof(arr) / sizeof(arr[0]);
    //打印原数组
    cout << "原数组：" << endl;
    for (int i = 0; i < size; i++)
        cout << arr[i] << " ";
    cout << endl;
    //调用线性计数排序函数
    CountSort(arr, size);
    //打印排序后的数组
    cout << "排序后的数组：" << endl;
    for (int i = 0; i < size; i++) 
        cout << arr[i] << " ";
    cout << endl;
    //返回0，表示程序正常结束
    return 0;
}