数据结构：非比较排序：计数排序

前面我们介绍的冒泡、选择、插入、归并、快排等排序算法本质上都属于比较排序——它们通过元素之间的两两比较来决定先后顺序。本篇我将带大家认识一种另辟蹊径的非比较排序算法——计数排序(Counting Sort)它不靠比较而是借助数组下标直接定位元素位置在特定场景下能达到线性时间复杂度。计数排序计数原理又称为鸽巢原理, 是对哈希直接定址法的变形应用. 操作步骤如下:统计相同元素出现次数根据统计的结果将序列回收到原来的序列中思路比如说有以下数组:我们统计每个元素出现的次数, 并将出现次数作为数据放到相应下标中.我们可以看到, 2出现了两次, 所以把2放在下标为2的地方, 3出现了两次, 把3放到下标为3的位置, 4出现了一次, 把1放到下标为4的位置, 6出现了三次, 把3放到下标6的位置, 而其他数字出现次数为0, 所以都放0.也就是说, 我们的数据变成了数组下标, 而相同数据出现次数变成了数据.我们再遍历新数组, 将它还原成一个有序数组.数据为0则往下遍历到下标为2的地方数据不为0则把下标还原为数据放回原数组中数据自减直到为0再去遍历下一个数据并把下标还原回来。思路很简单也可以说是间接利用了数组下标本来就是有序的这一特性很轻松地就把数组排序好了。但是存在一些场景问题。比如说我的数据是{102,103,101,102,103}。数据都比较大且分布集中开辟104个整型空间显然不合理其中101个空间数据都为0白白浪费掉了。我们可以先遍历一遍原数组找到最小值min和最大值max。我们实际存放数据的数组下标就是min到max范围之间我们只需要开辟max-min1个空间就好了将这块空间命名为count。我们如何放呢遍历一遍原数组用数据减去min得到下标让count数组中相应下标中的数据也就是统计原数据出现次数。统计完成后我们再还原回数组就好了。因为我们的下标是原数据减min得到的所以我们还原回去要把min加上。这样就排序好了。代码实现思路很简单我们来实现一下代码先遍历一遍原数组得到最大值和最小值。然后开辟大小为 max - min 1 的空间.这里不用 calloc 函数, 先用 malloc 函数然后用 memset 函数将 count 数组中的数据全设置为 0 也是可以的.然后我们遍历一遍数组, 数据减 min 等于 count 数组中哪个下标, 哪个下标数据就, 也就是 count[arr[i] - min]统计完之后我们把数据还原回数组. 需要遍历一遍 count 数组.代码就完成了.我们简单测试一下:结果符合预期代码没什么问题。时间复杂度可以发现计数排序时间效率很高虽然有嵌套循环但实际上时间复杂度为O(n)。但对于最大值和最小值相差很大的情况无可避免地会浪费掉大量空间所以该排序的适用场景也很有限。