8、计数排序
8.1 算法思想
思想：计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。
我们先看一下计数排序的动图：
计数排序实际上就是将数组中对应数据出现的次数，将数据出现次数映射到一个新数组中。在与数据相等值的下标处，将这个下标位置的元素自增。每出现一个数字就自增一次。
而平常的映射就是直接在其相等下标位置处理，叫做 绝对映射 ；还有一种映射方式叫 相对映射 。我们先看绝对映射。
绝对映射：
所谓绝对映射，就是开辟一个辅助数组 c c c ，数组大小为待排序数组的最大元素的大小 m a x max max 。
然后遍历数组，将数据映射到辅助数组 c c c 中。
然后根据 c o u n t count count 数组中的元素，根据元素对应的下标，将下标的值填入 a a a 数组中，如果 c o u n t count count 数组中该位置为 0 0 0， 则不需要填。
最后 a a a 数组中的元素就已经被排序好了。
其实讲到这里，大家也大约可以看出来 绝对映射 的缺点：当最大元素很大，或者是出现负数时，就无法映射了。因为空间开大了浪费空间，并且无法在负数下标自增。所以这就引出了 相对映射 。
相对映射：
相对映射，就是根据数据之间的相对情况来开辟数组大小，并在转换后的相对位置执行映射。
比如有这样一组数据： { 5000 , 5001 , 5500 , 5501 } \{5000, 5001, 5500, 5501\} {5000,5001,5500,5501} ，对于这组数据我们开 5501 5501 5501 个空间肯定是浪费的。
我们相对映射的思路就是遍历序列，找到序列最大值 m a x max max 和最小值 m i n min min ，然后开辟 m a x − m i n + 1 max - min + 1 max−min+1 个空间，让空间尽可能充分利用。
之后映射自增时，也使用相对位置，这个相对位置就是数组元素减去数组元素的最小值： a [ i ] − m i n a[i] - min a[i]−min 。
在最后将元素放到原数组中时，也需要将数组下标加上最小值： i + m i n i + min i+min 放回去就可以。
通过相对映射，对于元素有负数，和空间浪费的情况都可以解决。（ps：元素有负数的情况，无需特殊处理，因为相对映射的原因，这些步骤都可以正确进行，不信可以试验一下)。
8.2 代码实现
接下来，就使用相对映射的思路写出代码：
// 计数排序 正负数都可以排 void CountSort(int* a, int n) { // 1. 找最小值和最大值 int max = a[0], min = a[0]; for (int i = 0; i < n; i++) { if (a[i] > max) { max = a[i]; } if (a[i] < min) { min = a[i]; } } // 2. 根据差值构建 count 数组 int range = max - min + 1; int* count = (int*)malloc(sizeof(int) * range); if (count == NULL) { perror("malloc fail"); exit(-1); } // 初始化 memset(count, 0, sizeof(int) * range); // 3. 将值映射到count数组中 for (int i = 0; i < n; i++) { count[a[i] - min]++; // 映射到相对位置 } int cnt = 0; for (int i = 0; i < range; i++) { while (count[i]--) { a[cnt++] = i + min; } } }
8.3 时空复杂度
计数排序的时间复杂度其实是由 r a n g e range range 和 N N N 的关系来衡量的，当我们不确定 r a n g e range range 和 N N N 的大小时，我们可以认为 计数排序的时间复杂度为 O ( m a x ( N , r a n g e ) ) O(max(N, range)) O(max(N,range)) 。取较大的一个。
而空间复杂度则是 O ( r a n g e ) O(range) O(range)。
实际上通过时空复杂度上看，我们发现计数排序在数据集中的情况下是非常厉害的，能达到几乎 O ( N ) O(N) O(N) 的时间复杂度，并且空间复杂度也不会太大。但是对于范围分散，跨度大的序列就不适合，不仅时间没啥优势，空间占比也是个大问题。所以计数排序的适用范围是有限的。
四、排序算法复杂度及稳定性分析
这里我们就用两张图概括：
这里提一下排序的稳定性：
稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中， r [ i ] = r [ j ] r[i]=r[j] r[i]=r[j]，且 r [ i ] r[i] r[i] 在 r [ j ] r[j] r[j] 之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
稳定性是排序算法一种额外的优点。如果一种排序可以通过某种措施，达到数据相对次序不变的效果，则称该排序是稳定的。
五、排序性能测试框架
void TestOP() { srand(time(0)); const int N = 10000000; int* a1 = (int*)malloc(sizeof(int) * N); int* a2 = (int*)malloc(sizeof(int) * N); int* a3 = (int*)malloc(sizeof(int) * N); int* a4 = (int*)malloc(sizeof(int) * N); int* a5 = (int*)malloc(sizeof(int) * N); int* a6 = (int*)malloc(sizeof(int) * N); int* a7 = (int*)malloc(sizeof(int) * N); for (int i = 0; i < N; ++i) { a1[i] = rand(); a2[i] = a1[i]; a3[i] = a1[i]; a4[i] = a1[i]; a5[i] = a1[i]; a6[i] = a1[i]; a7[i] = a1[i]; } // clock 获取程序运行到这块的时间 // end1 - begin1 = 排序时间 // 获取的是毫秒 // 时间过小时，计算不出来 int begin1 = clock(); InsertSort(a1, N); int end1 = clock(); int begin2 = clock(); ShellSort(a2, N); int end2 = clock(); int begin3 = clock(); SelectSort(a3, N); int end3 = clock(); int begin4 = clock(); HeapSort(a4, N); int end4 = clock(); int begin5 = clock(); QuickSortT(a5, 0, N - 1); int end5 = clock(); int begin6 = clock(); BubbleSort(a6, N); int end6 = clock(); int begin7 = clock(); MergeSort(a7, N); MergeSortNonR(a7, N); int end7 = clock(); printf("InsertSort:%d\n", end1 - begin1); printf("ShellSort:%d\n", end2 - begin2); printf("SelectSort:%d\n", end3 - begin3); printf("HeapSort:%d\n", end4 - begin4); printf("QuickSort:%d\n", end5 - begin5); printf("BubbleSort:%d\n", end6 - begin6); printf("MergeSort:%d\n", end7 - begin7); free(a1); free(a2); free(a3); free(a4); free(a5); free(a6); free(a7); }
六、结语
到这里本篇博客就到此结束了，对于数据结构的学习，我们也就暂时告一段落了。
接下来 a n d u i n anduin anduin 更新的内容大多就是 C + + C++ C++ 和算法笔记了。
对于这篇文章，博主个人觉得还是不错的，希望你们阅读完之后可以有所收获！
如果小伙伴们需要源码的话，可以到我的 g i t e e gitee gitee 打包下载源码：八大排序
我们下期见~
