「数据结构」八大排序(超详解 附动图 源码)(18)

代码如下：
// 计数排序void CountSort(int* a, int n){ // 创建计数数组，数组大小为原数组中最大值-最小值 1 int max = a[0], min = a[0]; int i = 0; for (i = 0; i < n; i ) { if (a[i] > max) { max = a[i]; } if (a[i] < min) { min = a[i]; } } int range = max - min 1; int* count = (int*)malloc(sizeof(int) * range); // 初始化计数数组为0 memset(count, 0, range * 4); // 统计次数 for (i = 0; i < n; i ) { count[a[i] - min] ; } // 根据次数，进行排序 int j = 0; for (i = 0; i < range; i ) { while (count[i]--) { a[j ] = i min; } }}
注意：计数排序在排负数时，可将负数的类型转化成 unsigned int。
数组中元素有正有负的情况时不适用计数排序。
计数排序的特性总结：
计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。 时间复杂度：O(MAX(N,范围)) 空间复杂度：O(范围) 稳定性：稳定
排序算法复杂度及稳定性分析

注：在特殊情况下，排序的时间复杂度会发生变化，不能作为判断该排序是否稳定的依据。
稳定性：指数组中相同元素在排序后相对位置不发生变化。
例如：在冒泡排序中，相同元素比较时不会交换顺序，从而排序后相同元素的相对位置不会发生变化，所以冒泡排序是稳定的。
最后我们对各种排序算法进行一个简单的测试：随机测试10000个数据