经典排序—计数排序算法

vlambda
2022-03-11

经典排序—计数排序算法

大家好，我是李同学，今天我们来看看计数排序，计数排序是一个非常简单的排序算法。

一、前言

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

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

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

计数排序（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 <iostream>
   
     
     
   

   
     
     
   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;
   
     
     
   
}

输出：

五、算法分析

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

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

六、适用场景

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

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

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

好啦，今天的文章就到这啦,我们下期再见，拜了个拜！

·················END·················

vlambda博客
学习文章列表