经典排序—计数排序算法

欢迎大家来到IT世界,在知识的湖畔探索吧!

一、前言

我们知道归并排序是一种高效的排序算法，在任何情况下时间复杂度都为O(nlogn)。但是，它需要用额外的内存空间来暂时储存归并过程中的元素，因此我们可以认为归并排序是以牺牲一部分内存空间为代价来获得时间的高效性。

相反，如果内存空间有限，我们就必须以牺牲时间为代价来保证空间不被过度使用。像上面所说的那样，在设计一个算法的过程中同时考虑时间复杂度和空间复杂度，并且在这两者中找到一个平衡点的过程我们把它称作时空权衡（time and space trade-off）。

欢迎大家来到IT世界,在知识的湖畔探索吧!

在通常情况下，我们都认为时间更宝贵，而空间相对廉价。因此在大多数情况下，我们都是以牺牲空间的方式来减少运行时间。

计数排序（Counting Sort）是一个非基于比较的排序算法。而是通过计数的方式将时间复杂度降到了O(N)。

他快于任何比较排序算法。 当然这是一种牺牲空间换取时间的做法。它适用于范围较小的整数序列。

二、算法描述

按照从小到大排序的主要步骤：

第一步：找出原数组中元素值最大的，记为max，最小值记为 min。

第二步：创建一个新数组count，其长度是max – min + 1，其元素默认值都为0。

第三步：遍历原数组中的元素，以原数组中的元素作为count数组的索引，以原数组中的元素出现次数作为count数组的元素值。

第四步：创建结果数组result，其大小跟原始数组一样。

第五步：遍历count数组，将其对应的索引作为元素值填充到result数组中去。

第六步：返回结果数组result。

三、举个栗子

我们以从小到大排序为例，对下图所示的数组进行计数排序：

我们对其进行统计，统计结果如下：

看到这样的结果大家是不是有点懵？？？

下面我们将使用使用详细的步骤告诉大家这是怎么办到的。

我们通过最大值 – 最小值 + 1可得到计数数组的长度为： 7-0+1 = 8

通过我们的统计，count 结果如下：

在这个数组中，第一个位置存放的值为1，其表示的含义是值为0在原始数组中出现的次数为1次；第二个位置存放的元素是1，其表示的含义是值为1在原始数组中出现的次数为1次；第三个位置存放的元素是2，其表示的含义是值为2在原始数组中出现的次数为2次，以此类推…..

创建数组 result :

遍历count数组进行排序：

我们根据统计结果对其排序，如下图所示，红色结点表示已经排序的值。

四、算法实现

#include       using namespace std; int Arr[] = {3,3,5,2,1,0,7,2,5,4,4,7,3}; int cnt[8]; int main(){ for (int i=0; i<13; i++){ cnt[Arr[i]]++; } for(int i=0; i<8; i++){ for(int j=0; j<cnt[i]; j++){ cout << i << " "; } } return 0; }   

欢迎大家来到IT世界,在知识的湖畔探索吧!

输出：

五、算法分析

时间复杂度：O(n+k)，整个过程需要遍历两次数组，一次是遍历长度为 n的数组，另一次是从计数器（假设有k个计数器）中遍历，因此时间复杂度为O(n+k)

空间复杂度：O(k)，在计数排序的过程中用到了长度为k的额外数组，故空间复杂度为 O(k) 。

六、适用场景

待排序数组是在一定范围内的整数可以选择计数排序。

虽然计数排序效率不错但是用到的并不多。

• 这是因为其当数组元素的范围太大时，并不适合计数排序，不仅浪费时间，效率还会大大降低。
• 当待排序的元素非整数时,也不适用,大家思考一下这是为什么呢?