编写函数实现计数排序算法c++

计数排序（Counting Sort）是一种非比较型的排序算法，它利用了待排数据的取值范围较小的特点，在时间复杂度为 O(n+k) 的情况下完成了排序。

以下是 C++ 代码实现：

void countingSort(int arr[], int n) {
    if (n <= 1) return;
    int maxVal = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > maxVal) {
            maxVal = arr[i];
        }
    }
    int* cnt = new int[maxVal + 1];
    memset(cnt, 0, (maxVal + 1) * sizeof(int));
    for (int i = 0; i < n; i++) {
        cnt[arr[i]]++;
    }
    for (int i = 1; i <= maxVal; i++) {
        cnt[i] += cnt[i - 1];
    }
    int* tmp = new int[n];
    for (int i = n - 1; i >= 0; i--) {
        tmp[cnt[arr[i]] - 1] = arr[i];
        cnt[arr[i]]--;
    }
    memcpy(arr, tmp, n * sizeof(int));
    delete[] cnt;
    delete[] tmp;
}

其中，`arr` 是待排序数组，`n` 是数组长度。首先找出待排数据中的最大值 `maxVal`，然后创建一个大小为 `maxVal + 1` 的计数数组 `cnt`，并将其初始化为 0。接着遍历待排数组，统计每个元素出现的次数，并存储到 `cnt` 数组中。然后遍历 `cnt` 数组，将其前缀和计算出来。接着创建一个临时数组 `tmp`，从待排数组的末尾开始遍历，通过 `cnt` 数组将元素存储到 `tmp` 数组中。最后将 `tmp` 数组复制回 `arr` 数组，完成排序。需要注意的是，在函数结束时需要释放动态分配的内存。