这里就会有两个问题想问一下大家:
怎么将待排序的数组中的数字映射到计数的数组中?
如何将计数数组中的元素回写到待待排序的数组中,从而达到排序的效果?...2.1 绝对位置和相对位置
绝对位置:从数组首元素开始计算,剩余每个元素的位置都是按照数组首元素为参照的。...举个例子:数组a:[1,5,6,8,9,7,3,2,0,4],那对于计数数组来说用绝对位置就比较好,原因是这个待排序的数组a的元素最小值是为0,最大值为9,这里用绝对位置就比较舒服!...(利用相对位置进行对应)
void CountSort(int* a, int n)
{
//1.为获得相对位置,我们要想找到数组中的最小值还要找最大值
int min = a[0],max...由于不涉及元素之间的比较,计数排序可以在较小的数据范围内达到比比较类排序更高效的结果。
空间复杂度:额外的空间复杂度为
O(k)
,因为需要创建一个计数数组用来记录元素的出现次数和累积结果。