三分钟彻底理解计数排序
作者 | 本余
来源 | blog.csdn.net/qq_42111463
一、计数排序
计数排序平均时间复杂度：o(n+k)(平方)、空间复杂度：o(k)、稳定排序、外部排序
1.1 算法描述
计数排序，不是基于元素比较，而是利用数组下标确定元素的正确位置。
1.2 排序演示
待排序列：9 3 5 4 9 1 2 7 8 1 3 6 5 3 4 0 10 9 7 9 先便利这个无序的数列，让每一个整数按照值对号入座，对应数组下标的元素加1。统计结果如下图所示：数组值：|1 2 1 3 2 2 1 2 1 4 1| 下表值：|0 1 2 3 4 5 6 7 8 9 10| 直接便利数组，输出数组元素的下标值，元素的值是几就输出多少次。输出结果为：0 1 1 2 3 3 3 4 4 5 5 6 7 7 8 9 9 9 10 注意事项：1.计数排序时只以序列的最大值来作为统计数组的长度是不对的，比如排序95 94 96…，这个时候我们可以用数列最大值和最小值得差值加1（max-min+1）作为统计数组的长度。2.在现实排序中，比如给学生的分数排序，遇到相同的分数就会分不清谁是谁。姓名 成绩 张三 90 李四 99 王五 95 赵六 94 李七 95 统计数组变化如下：这样相加的目的，是让统计数组存储的元素值，等于相应整数的最终排序位置。比如下标是9的元素值为5，代表原始数列的整数9，最终的排序是在第5位。接下来，我们创建输出数组sortedArray，长度和输入数列一致。然后从后向前遍历输入数列：第一步，我们遍历成绩表最后一行的李七：李七是95分，我们找到countArray下标是5的元素，值是4，代表李七的成绩排名位置在第4位。同时，我们给countArray下标是5的元素值减1，从4变成3,，代表着下次再遇到95分的成绩时，最终排名是第3。
第二步，我们遍历成绩表倒数第二行的赵六：赵六是94分，我们找到countArray下标是4的元素，值是2，代表小白的成绩排名位置在第2位。同时，我们给countArray下标是4的元素值减1，从2变成1,，代表着下次再遇到94分的成绩时（实际上已经遇不到了），最终排名是第1。
依次排序最终结果为：
1.3 代码展示
int* countSort(int* arr,int len)
{
int max = arr[0];//记录数列的最大值
int min = arr[0];//记录数列的最小值
for(int i=0;i<len-1;i++)
{
if(arr[i]>max)
{
max = arr[i];
}
if(arr[i]<min)
{
min = arr[i];
}
}
int l = max-min;//计算出数列最大最小值得差值
int* couarr = new int[l+1];
for(int i=0;i<len;i++)
{
couarr[arr[i]-min]++;//统计元素个数
}
int sum = 0;
for(int i=0;i<l+1;i++)//统计数组做变形，后面的元素等于前面元素的和
{
sum += couarr[i];
couarr[i]=sum;
}
int* sortarr = new int[len];
for(int i=len-1;i>=0;i--)//倒序遍历原始数组，从统计数组中找到正确位置
{
sortarr[couarr[arr[i]-min]-1]=arr[i];
couarr[arr[i]-min]--;
}
delete couarr;
return sortarr;
}