“计数”排序

大家好，欢迎来到IT知识分享网。

一、什么是计数排序？

计数排序，是通过统计每一个数字出现的次数，并把它映射到与它自己本身数值相同的下标处，再遍历映射的数组使原数组有序的一种排序方法，计数排序的本质是一种哈希算法，也就是通过建立映射关系来达到排序的目的。

二、如何实现计数排序？

基本思路：先开辟一个映射数组，然后遍历原数组，数组中的元素是几就在开辟的的映射数组下标为几的位置+1。得到的这个映射数组就包含了原数组中所有元素的映射关系。遍历一遍映射数组找出原数组中出现过的数即可。

参考代码如下：

void CountSort(int* a, int n) { 
    assert(a); int i = 0; int max = a[0]; int min = a[0]; //找出最大最小值，算出需要开辟多大的空间 for (i = 1; i < n; i++) { 
    if (a[i] > max) { 
    max = a[i]; } if (a[i] < min) { 
    min = a[i]; } } //需要开辟的空间的大小range int range = max - min + 1; int* CountArr = (int*)malloc(sizeof(int) * range); if (CountArr == NULL) { 
    perror(" "); return; } //一定要先初始化为0，不然的话是随机数就会影响统计的结果 memset(CountArr, 0, sizeof(int) * range); //遍历数组，给映射数组对应的位置统计数组出现的次数 for (i = 0; i < n; i++) { 
    //减去min是它的相对映射的位置 CountArr[a[i] - min]++; } //遍历映射数组 int j = 0; for (i = 0; i < range; i++) { 
    //对应的位置是几就把这个数字往原数组中填几次 while (CountArr[i]--) { 
    //由于上面在映射的时候减去了min，所以在重新 //写回数组的时候需要加上min得到原来的值 a[j++] = i + min; } } free(CountArr); CountArr = NULL; } 

三、适用场景

尽管相对映射能处理一些相对集中的元素的排序的问题，但也只是解决了相对较为集中的元素的排序的问题，如果一个数组的数是很分散的，例如：1，100，102，104，那这个相对映射方法依然没办法很好地减少内存的消耗，所以计数排序是具有局限性的，只适合元素相对较为集中的数组的排序，而且只能排整数，不能排其他类型的数据，如浮点数等等。因为下标只能是整数。对于相对映射是可以对负数进行排序的，因为无论如何最小的那个元素都是映射到0的位置的，不会越界，但是绝对映射不能对负数排序，不然的话下标访问负数就一定会越界访问的。所以计数排序的使用场景还是很局限的。

四、时间复杂度和空间复杂度

以上就是计数排序的全部内容，你学会了吗？如果对你有所帮助，那就点亮一下小心心，顺便点点关注呗！我们下期见！！！