编辑代码

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 计数排序
void countingSort(vector<int>& arr) {
    int maxVal = *max_element(arr.begin(), arr.end());
    int minVal = *min_element(arr.begin(), arr.end());
    int range = maxVal - minVal + 1;

    vector<int> count(range, 0);
    vector<int> output(arr.size());

    // 计算每个元素的频率
    for (int i = 0; i < arr.size(); i++)
        count[arr[i] - minVal]++;

    // 计算累计频率
    for (int i = 1; i < range; i++)
        count[i] += count[i - 1];

    // 根据频率将元素放到输出数组中
    for (int i = arr.size() - 1; i >= 0; i--) {
        output[count[arr[i] - minVal] - 1] = arr[i];
        count[arr[i] - minVal]--;
    }

    // 将排序好的数组复制回原数组
    for (int i = 0; i < arr.size(); i++)
        arr[i] = output[i];
}

// 线性计数排序
void linearCountingSort(vector<int>& arr) {
    int maxVal = *max_element(arr.begin(), arr.end());
    int minVal = *min_element(arr.begin(), arr.end());
    int range = maxVal - minVal + 1;

    vector<int> count(range, 0);
    vector<int> output(arr.size());

    // 计算每个元素的频率
    for (int i = 0; i < arr.size(); i++)
        count[arr[i] - minVal]++;

    // 根据频率将元素放到输出数组中
    int j = 0;
    for (int i = 0; i < range; i++) {
        while (count[i] > 0) {
            output[j] = i + minVal;
            count[i]--;
            j++;
        }
    }

    // 将排序好的数组复制回原数组
    for (int i = 0; i < arr.size(); i++)
        arr[i] = output[i];
}

// 打印数组
void printArray(const vector<int>& arr) {
    for (int num : arr)
        cout << num << " ";
    cout << endl;
}

int main() {
    vector<int> arr = {4, 2, 7, 1, 9, 5, 3, 8, 6};
    
    cout << "Original array: ";
    printArray(arr);

    countingSort(arr);

    cout << "Counting Sort: ";
    printArray(arr);

    vector<int> arrLinear = {4, 2, 7, 1, 9, 5, 3, 8, 6};
    
    cout << "Original array: ";
    printArray(arrLinear);

    linearCountingSort(arrLinear);

    cout << "Linear Counting Sort: ";
    printArray(arrLinear);

    return 0;
}