C++ 计数排序实例详解
计数排序是一种非比较的排序算法，具有很高的时间效率，特别是在处理大规模整数数组时。下面将详细介绍计数排序的原理、实现和优缺点。
计数排序的原理
计数排序的核心思想是使用一个辅助数组来统计每个整数出现的次数，然后根据统计结果将原数组排序。具体来说，计数排序的步骤可以分为以下几个步骤：
1. 找到数组中的最大值和最小值，以确定辅助数组的大小。
2. 创建一个辅助数组，大小为最大值减去最小值加一。
3. 遍历原数组，对每个整数进行统计，统计结果存储在辅助数组中。
4. 遍历辅助数组，将统计结果写回到原数组中。
计数排序的实现
下面是一个简单的计数排序的实现：
```c
void CountSort(int* a, size_t size) {
assert(a);
size_t max = a[0];
size_t min = a[0];
for (size_t i = 0; i < size; ++i) {
if (a[i] > max) {
max = a[i];
}
if (a[i] < min) {
min = a[i];
}
}
size_t range = max - min + 1;
size_t* count = new size_t[range];
memset(count, 0, sizeof(size_t)*range);
for (size_t i = 0; i < size; ++i) {
count[a[i]-min]++;
}
size_t index = 0;
for (size_t i = 0; i < range; ++i) {
while (count[i]--) {
a[index++] = i + min;
}
}
delete[] count;
}
```
优点
计数排序的主要优点是时间效率高，特别是在处理大规模整数数组时。由于计数排序不需要比较，因此可以避免比较排序算法的时间复杂度限制。
缺点
计数排序的主要缺点是需要牺牲空间换取时间，特别是在处理大规模整数数组时。另外，计数排序只能用于对无符号整形排序。
时间复杂度
计数排序的时间复杂度为O(N+K)，其中K为整数在范围。
空间复杂度
计数排序的空间复杂度为O(最大数-最小数)，其中最大数和最小数是数组中的最大值和最小值。
性能
计数排序是一种稳定排序，性能非常高，特别是在处理大规模整数数组时。
计数排序是一种非常有用的排序算法，特别是在处理大规模整数数组时。然而，需要注意的是，计数排序需要牺牲空间换取时间，且只能用于对无符号整形排序。
