什么是计数排序算法？

计数排序（Counting Sort）是一种非比较排序算法，时间复杂度为O(n+k)，其中k为输入的数据范围。计数排序的核心思想是统计每个元素在输入序列中出现的次数，然后根据元素出现的次数将输入序列中的元素排列。计数排序适用于数据范围比较小的情况，当k=O(n)时，计数排序可以在O(n)的时间复杂度内完成排序。

下面是计数排序的C++实现代码：

#include <iostream>
#include <vector>

using namespace std;

void countingSort(vector<int>& arr) {
    int n = arr.size();
    if (n <= 1) return;

    // 找出最大值max和最小值min
    int max = arr[0], min = arr[0];
    for (int i = 1; i < n; ++i) {
        if (arr[i] > max) max = arr[i];
        if (arr[i] < min) min = arr[i];
    }

    // 统计元素出现的次数
    int range = max - min + 1;
    vector<int> count(range, 0);
    for (int i = 0; i < n; ++i) {
        count[arr[i] - min]++;
    }

    // 计算元素的位置
    for (int i = 1; i < range; ++i) {
        count[i] += count[i - 1];
    }

    // 将元素按照位置存储在新数组中
    vector<int> res(n, 0);
    for (int i = n - 1; i >= 0; --i) {
        int index = count[arr[i] - min] - 1;
        res[index] = arr[i];
        count[arr[i] - min]--;
    }

    // 将结果拷贝回原数组
    for (int i = 0; i < n; ++i) {
        arr[i] = res[i];
    }
}

int main() {
    vector<int> arr = {3, 6, 2, 4, 3, 9, 1, 5, 7, 8};
    countingSort(arr);
    for (int i = 0; i < arr.size(); ++i) {
        cout << arr[i] << " ";
    }
    cout << endl;
    return 0;
}

代码中，我们首先找到输入数组中的最大值max和最小值min，然后根据它们计算出数值范围range。我们使用一个大小为range的数组count来统计每个元素在输入序列中出现的次数。接下来，我们计算元素的位置，即将count数组转化为每个元素在输出数组中的起始下标。最后，我们将元素按照位置存储在新数组中，并将结果拷贝回原数组。

在计数排序算法中，最重要的步骤是统计元素出现的次数和计算元素的位置。由于计数排序的核心思想是统计元素出现的次数，因此计数排序只适用于元素均为非负整数的情况。如果输入序列中存在负数，可以通过将所有元素加上一个正数k，使得所有元素均为非负数，然后再进行排序。在排序完成后，我们需要将结果数组拷贝回原数组。

下面是计数排序算法的详细步骤：

1. 找到输入数组中的最大值max和最小值min，根据它们计算出数值范围range。

2. 使用一个大小为range的数组count来统计每个元素在输入序列中出现的次数。

3. 计算元素的位置，即将count数组转化为每个元素在输出数组中的起始下标。

4. 将元素按照位置存储在新数组中。

5. 将结果拷贝回原数组。

计数排序算法的时间复杂度为O(n+k)，其中n为输入序列的长度，k为数值范围。计数排序算法是一种稳定的排序算法，因为对于输入序列中相同的元素，计数排序算法会按照它们在输入序列中的相对顺序将它们排列在输出序列中的相对位置上。

注意：在计数排序算法的实现中，我们使用了vector容器来存储输入序列和输出序列，并且使用了vector容器的一些常用操作，如size()和operator[]。如果需要使用原始数组实现计数排序算法，需要自己实现相应的函数和操作。

C++语言实现计数排序算法的代码，包括了详细的注释：

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

void CountSort(vector<int>& arr) {
    int n = arr.size();
    if (n <= 1) {
        return;
    }

    // 找到最大值和最小值，计算出数值范围range
    int max_val = arr[0];
    int min_val = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max_val) {
            max_val = arr[i];
        }
        if (arr[i] < min_val) {
            min_val = arr[i];
        }
    }
    int range = max_val - min_val + 1;

    // 初始化计数数组count，并统计每个元素在输入序列中出现的次数
    vector<int> count(range, 0);
    for (int i = 0; i < n; i++) {
        count[arr[i] - min_val]++;
    }

    // 计算每个元素的位置，即将count数组转化为每个元素在输出数组中的起始下标
    for (int i = 1; i < range; i++) {
        count[i] += count[i-1];
    }

    // 将元素按照位置存储在新数组中
    vector<int> sorted(n, 0);
    for (int i = n-1; i >= 0; i--) {
        sorted[count[arr[i] - min_val] - 1] = arr[i];
        count[arr[i] - min_val]--;
    }

    // 将结果拷贝回原数组
    for (int i = 0; i < n; i++) {
        arr[i] = sorted[i];
    }
}

int main() {
    vector<int> arr = {5, 2, 9, 4, 7, 6, 1, 3, 8};
    CountSort(arr);
    for (int i = 0; i < arr.size(); i++) {
        cout << arr[i] << " ";
    }
    return 0;
}

在主函数中，我们初始化了一个包含9个整数的vector容器，用于存储输入序列。然后，我们调用CountSort函数，对输入序列进行排序。最后，我们使用一个for循环遍历排序后的序列，并输出每个元素的值。

#include <iostream>

using namespace std;

void CountSort(int arr[], int n) {
    // 找到输入数组中的最大值
    int max_value = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max_value) {
            max_value = arr[i];
        }
    }

    // 创建计数数组，并将其所有元素初始化为0
    int count[max_value + 1] = {0};

    // 统计输入数组中每个元素出现的次数
    for (int i = 0; i < n; i++) {
        count[arr[i]]++;
    }

    // 累加计数数组中的元素，以便确定每个元素在输出数组中的位置
    for (int i = 1; i <= max_value; i++) {
        count[i] += count[i - 1];
    }

    // 创建输出数组，并将输入数组中的元素按顺序放入输出数组中
    int output[n];
    for (int i = n - 1; i >= 0; i--) {
        output[count[arr[i]] - 1] = arr[i];
        count[arr[i]]--;
    }

    // 将输出数组中的元素拷贝回输入数组中
    for (int i = 0; i < n; i++) {
        arr[i] = output[i];
    }
}

int main() {
    int arr[] = {5, 2, 9, 4, 7, 6, 1, 3, 8, 5, 8, 5, 9, 5, 8, 5, 8, 9};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "Original array: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    CountSort(arr, n);

    cout << "Sorted array: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}

计数排序（Counting Sort）是一种非比较排序算法，它的时间复杂度为O(n+k)，其中n是输入数组的长度，k是输入数组中元素的范围。与其他常见的排序算法（如快速排序、归并排序）相比，计数排序的时间复杂度较低，但它需要额外的空间来存储计数数组和输出数组。

计数排序的基本思想是：首先找到输入数组中的最大值max_value，然后创建一个大小为max_value+1的计数数组，将输入数组中每个元素出现的次数存储在计数数组中。接着，遍历计数数组，将它们的元素相加，从而获得了每个元素在输出数组中的正确位置。最后，遍历输入数组，将每个元素按照计数数组中的顺序放入输出数组中。

具体地，计数排序的算法步骤如下：

1. 找到输入数组中的最大值max_value。

2. 创建大小为max_value+1的计数数组，并将其所有元素初始化为0。

3. 遍历输入数组，统计每个元素出现的次数，并将其存储在计数数组中。

4. 遍历计数数组，将每个元素加上前面所有元素的值，从而获得了每个元素在输出数组中的位置。

5. 创建一个与输入数组相同大小的输出数组。

6. 遍历输入数组，将每个元素按照计数数组中的顺序放入输出数组中。

7. 将输出数组拷贝回输入数组中。

值得注意的是，如果输入数组中有相同的元素，它们会被放在输出数组中相邻的位置上。因此，计数排序是一种稳定的排序算法。

计数排序的优点是它的时间复杂度为O(n+k)，而且可以应用于小范围整数排序的场景，例如给定一个年龄序列，要求按照年龄大小排序。然而，计数排序的缺点是它需要额外的空间来存储计数数组和输出数组，因此当输入数组的范围很大时，计数排序的空间复杂度会很高，可能导致算法无法实际应用。