—计数排序—
计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数
算法描述
具体算法描述如下：
- <1>. 找出待排序的数组中最大和最小的元素；
- <2>. 统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
- <3>. 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；
- <4>. 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。
代码实现
void Count_Sort(int a[], int n)
{
// 找到最大元素
int max = a[0];
for (int i = 1; i < n; ++i)
{
if (a[i] > max)
max = a[i];
}
// 创建计数数组
int* CountArr = new int[max + 1];
//初始化0数组
for (int i = 0; i < max + 1; ++i)
{
CountArr[i] = 0;
}
// 计数
for (int i = 0; i < n; ++i)
CountArr[a[i]]++;
//累积
for (int i = 1; i < max + 1; ++i)
{
CountArr[i] += CountArr[i - 1];
}
//创建结果数组
int* OutPut = new int[n];
for (int i = 0; i < n; ++i)
{
OutPut[CountArr[a[i]] - 1] = a[i];
CountArr[a[i]]--;
}
//赋值
for (int i = 0; i < n; i++)
a[i] = OutPut[i];
}
算法分析
当输入的元素是n 个0到k之间的整数时，它的运行时间是 O(n + k)。计数排序不是比较排序，排序的速度快于任何比较排序算法。由于用来计数的数组C的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小 值的差加上1），这使得计数排序对于数据范围很大的数组，需要大量时间和内存。
- 平均情况：T(n) = O(n+k)
最佳情况：T(n) = O(n+k)
最差情况：T(n) = O(n+k)
稳定性
- 稳定
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 351134995@qq.com
