计数排序(Counting Sort)算法是不需进行比较的排序算法,顾名思义,它会去数元素的数量来进行排序。这种排序法只需要线性时间和空间的复杂度就可以完成排序,比时间复杂度为 O(nlogn) 的算法还快,而且作法也不会太难。虽然如此,计数排序法并不算是常见的排序算法,因为它只能用来排序已知数值范围的串行(由于要直接对应串行的索引值,所以这组数值通常会是一组整数)。举例来说,已知串行中的每个元素(或是其它要用来作为排序依据的属性)是数值范围 n 到 m 中的任一整数,那么我们便可以使用计数排序法来排序这个串行。

计数排序法(Counting Sort)

计数排序法的概念

计数排序法排序元素的方式并不是去「比较」两元素间的大小,而是先去计算每个元素(或是其作为排序依据的属性)在串行中出现的次数,再利用这个次数信息去进行更进一步的排序,以下将说明两种不同的应用情形。

首先,第一种作法是,在取得次数信息之后,直接把已知的那一组数值中的数,依序根据其出现的次数填写到原本要排序的串行中,填写完成后该串行也就排序完了。

举例来说,已知串行中的元素均为 1, 2, 3, 4 的其中一个数值。这个串行中实际保存的数据为 [3, 2, 1, 2, 3, 3, 1],我们可以先计算出这个串行共有 2 个 1、2 个 2、3 个 3、和 0 个 4。

接着就开始把数值依序填进这个相同的串行中,首先填入 2 个 1,串行内容会变成 [1, 1, 1, 2, 3, 3, 1]。再来填入 2 个 2,串行内容会变成 [1, 1, 2, 2, 3, 3, 1]。再来填入 3 个 3,串行内容会变成 [1, 1, 2, 2, 3, 3, 3]。最后的 4 由于原先就没有出现,所以不用填写,此时就完成这个串行的排序了。

这样的排序方式十分简单快速,属于「原地」(in-place)的作法,适用在被排序的元素就是用来作为排序依据的数值。也就是说,若要排序一个整数数组的话,可以直接使用这个方式。虽然这个排序方式不是稳定的,那也不重要,因为它本来就只能排序像整数这样的纯量类型。

接着,来说明一下第二种作法。第二种作法可以说是第一种作法的延伸,在取得次数信息之后,还要先利用这个次数信息来计算出元素的位置信息。同样以刚才的串行来举例 [3, 2, 1, 2, 3, 3, 1],次数信息为 2 个 1、2 个 2、3 个 3、和 0 个 4,所以我们可以借由照顺序走访并累加每次迭代时的此项和前项的次数,来得出「有 2 + 0 = 2 个元素小于等于 1」、「有 2 + 2 = 4 个元素小于等于 2」、「有 4 + 3 = 7 个元素小于等于 3」、「有 7 + 0 = 7 个元素小于等于 4」这样的位置信息。

接着产生出另一个相同大小的空串行,并从原串行的尾端向前开始走访这个原串行,一开始会看到元素 1,根据位置信息「有 2 个元素小于等于 1」,我们可以直接把这个原串行的元素 1 拷贝进新串行的第 2 个位置(也就是索引 1 的位置),此时新串行的内容为 [?, 1, ?, ?, ?, ?, ?],且位置信息修改为「有 2 - 1 = 1 个元素小于等于 1」,然后再继续下次的迭代,重复一样的动作,排序的结果就会存在新串行中了。

您可能会问:为什么要从原串行的尾端向前开始走访,而不是从头开始呢?这是为了要保持相同元素之间的顺序,来达成稳定排序的目的。

第二种排序方式要比第一种稍微复杂一点,而且会需要额外的空间来保存结果,属于「非原地」(out-of-place)的作法,但其适用于「用来作为排序依据的数值不直接是被排序的元素,而是该元素的某个属性」的情形,且排序结果是稳定的。

计数排序法的过程

假设现在有个数组数据,内容如下:

索引    0   1   2   3   4   5   6   7   8
数值    9   8   3   3   9   2   4   6   3

要如何将它递增排列呢?

由于现在要排序的数据是整数数据,因此前面提到的第一种(不稳定)和第二种(稳定)的计数排序法皆可以使用。

然而不管使用哪种方式,都要先计算出数值组中的各项数值在数组中出现的次数。

由于待排序数组的元素都是 0~9 中的一个整数数值,因此数组元素有 (9 - 0 + 1) = 10 种可能的数值,所以要创建出一个大小为 10 的整数数组来保存计数排序法要用的次数信息。此数组索引 i 的位置用来保存元素 i 在待排序数组中出现的次数。计算之后我们得到了如下的计数数组:

索引(数值)    0   1   2   3   4   5   6   7   8   9
数值(次数)    0   0   1   3   1   0   1   0   1   2
第一种计数排序法(不稳定)

利用次数信息开始将元素值填写进原数组中。

由于 0 和 1 的数量都是 0,因此无需填写到原数组中。

       ○
数值    0   1   2   3   4   5   6   7   8   9
次数    0   0   1   3   1   0   1   0   1   2
---------------------------------------------
索引    0   1   2   3   4   5   6   7   8 
数值    9   8   3   3   9   2   4   6   3
       ●

       ○  ○
数值    0   1   2   3   4   5   6   7   8   9
次数    0   0   1   3   1   0   1   0   1   2
---------------------------------------------
索引    0   1   2   3   4   5   6   7   8 
数值    9   8   3   3   9   2   4   6   3
       ●

将 1 个 2 填写到原数组中。

       ○  ○  ○
数值    0   1   2   3   4   5   6   7   8   9
次数    0   0   1   3   1   0   1   0   1   2
---------------------------------------------
索引    0   1   2   3   4   5   6   7   8 
数值    2   8   3   3   9   2   4   6   3
       ○  ●

将 3 个 3 填写到原数组中。

       ○  ○  ○  ○
数值    0   1   2   3   4   5   6   7   8   9
次数    0   0   1   3   1   0   1   0   1   2
---------------------------------------------
索引    0   1   2   3   4   5   6   7   8 
数值    2   3   3   3   9   2   4   6   3
       ○  ○  ○  ○  ●

将 1 个 4 填写到原数组中。

       ○  ○  ○  ○  ○
数值    0   1   2   3   4   5   6   7   8   9
次数    0   0   1   3   1   0   1   0   1   2
---------------------------------------------
索引    0   1   2   3   4   5   6   7   8 
数值    2   3   3   3   4   2   4   6   3
       ○  ○  ○  ○  ○  ●

由于 5 的数量是 0,因此无需填写到原数组中。

       ○  ○  ○  ○  ○  ○
数值    0   1   2   3   4   5   6   7   8   9
次数    0   0   1   3   1   0   1   0   1   2
---------------------------------------------
索引    0   1   2   3   4   5   6   7   8 
数值    2   3   3   3   4   2   4   6   3
       ○  ○  ○  ○  ○  ●

将 1 个 6 填写到原数组中。

       ○  ○  ○  ○  ○  ○  ○
数值    0   1   2   3   4   5   6   7   8   9
次数    0   0   1   3   1   0   1   0   1   2
---------------------------------------------
索引    0   1   2   3   4   5   6   7   8 
数值    2   3   3   3   4   6   4   6   3
       ○  ○  ○  ○  ○  ○  ●

由于 7 的数量是 0,因此无需填写到原数组中。

       ○  ○  ○  ○  ○  ○  ○  ○
数值    0   1   2   3   4   5   6   7   8   9
次数    0   0   1   3   1   0   1   0   1   2
---------------------------------------------
索引    0   1   2   3   4   5   6   7   8 
数值    2   3   3   3   4   6   4   6   3
       ○  ○  ○  ○  ○  ○  ●

将 1 个 8 填写到原数组中。

       ○  ○  ○  ○  ○  ○  ○  ○  ○
数值    0   1   2   3   4   5   6   7   8   9
次数    0   0   1   3   1   0   1   0   1   2
---------------------------------------------
索引    0   1   2   3   4   5   6   7   8 
数值    2   3   3   3   4   6   8   6   3
       ○  ○  ○  ○  ○  ○  ○  ●

将 2 个 9 填写到原数组中。

       ○  ○  ○  ○  ○  ○  ○  ○  ○  ○
数值    0   1   2   3   4   5   6   7   8   9
次数    0   0   1   3   1   0   1   0   1   2
---------------------------------------------
索引    0   1   2   3   4   5   6   7   8 
数值    2   3   3   3   4   6   8   9   9
       ○  ○  ○  ○  ○  ○  ○  ○  ○

依计数数组把元素填回原数组

第二种计数排序法(稳定)

累加计数数组来求出元素的位置信息。

                 ●
索引(数值)    0   1   2   3   4   5   6   7   8   9
数值(位置)    0   0   1   3   1   0   1   0   1   2
             └+┘

                     ●
索引(数值)    0   1   2   3   4   5   6   7   8   9
数值(位置)    0   0   1   3   1   0   1   0   1   2
                 └+┘

                         ●
索引(数值)    0   1   2   3   4   5   6   7   8   9
数值(位置)    0   0   1   3   1   0   1   0   1   2
                     └+┘

                             ●
索引(数值)    0   1   2   3   4   5   6   7   8   9
数值(位置)    0   0   1   4   1   0   1   0   1   2
                         └+┘

                                 ●
索引(数值)    0   1   2   3   4   5   6   7   8   9
数值(位置)    0   0   1   4   5   0   1   0   1   2
                             └+┘

                                     ●
索引(数值)    0   1   2   3   4   5   6   7   8   9
数值(位置)    0   0   1   4   5   5   1   0   1   2
                                 └+┘

                                         ●
索引(数值)    0   1   2   3   4   5   6   7   8   9
数值(位置)    0   0   1   4   5   5   6   0   1   2
                                     └+┘

                                             ●
索引(数值)    0   1   2   3   4   5   6   7   8   9
数值(位置)    0   0   1   4   5   5   6   6   1   2
                                         └+┘

                                                 ●
索引(数值)    0   1   2   3   4   5   6   7   8   9
数值(位置)    0   0   1   4   5   5   6   6   7   2
                                             └+┘

                                                     ●
索引(数值)    0   1   2   3   4   5   6   7   8   9
数值(位置)    0   0   1   4   5   5   6   6   7   9

累加后的计数数组

创建与待排序数组同等大小的新数组。

索引    0   1   2   3   4   5   6   7   8 
数值    ?   ?   ?   ?   ?   ?   ?   ?   ?

从原来待排序数组的尾端开始将所有元素放入新数组。

                   ●
数值    0   1   2   3   4   5   6   7   8   9
位置    0   0   1   4↓ 5   5   6   6   7   9
----------------------------------------------
                                       ●
索引    0   1   2   3   4   5   6   7   8
数值    9   8   3   3   9   2   4   6   3
----------------------------------------------
                   ○
索引    0   1   2   3   4   5   6   7   8
数值    ?   ?   ?   3   ?   ?   ?   ?   ?

                               ●
数值    0   1   2   3   4   5   6   7   8   9
位置    0   0   1   3   5   5   6↓ 6   7   9
----------------------------------------------
                                   ●
索引    0   1   2   3   4   5   6   7   8
数值    9   8   3   3   9   2   4   6   3
----------------------------------------------
                   ○      ○ 
索引    0   1   2   3   4   5   6   7   8
数值    ?   ?   ?   3   ?   6   ?   ?   ?

                       ●
数值    0   1   2   3   4   5   6   7   8   9
位置    0   0   1   3   5↓ 5   5   6   7   9
----------------------------------------------
                               ●
索引    0   1   2   3   4   5   6   7   8
数值    9   8   3   3   9   2   4   6   3
----------------------------------------------
                   ○  ○  ○ 
索引    0   1   2   3   4   5   6   7   8
数值    ?   ?   ?   3   4   6   ?   ?   ?

               ●
数值    0   1   2   3   4   5   6   7   8   9
位置    0   0   1↓ 3   4   5   5   6   7   9
----------------------------------------------
                           ●
索引    0   1   2   3   4   5   6   7   8
数值    9   8   3   3   9   2   4   6   3
----------------------------------------------
       ○          ○  ○  ○ 
索引    0   1   2   3   4   5   6   7   8
数值    2   ?   ?   3   4   6   ?   ?   ?

                                           ●
数值    0   1   2   3   4   5   6   7   8   9
位置    0   0   0   3   4   5   5   6   7   9↓
----------------------------------------------
                       ●
索引    0   1   2   3   4   5   6   7   8
数值    9   8   3   3   9   2   4   6   3
----------------------------------------------
       ○          ○  ○  ○          ○
索引    0   1   2   3   4   5   6   7   8
数值    2   ?   ?   3   4   6   ?   ?   9

                   ●
数值    0   1   2   3   4   5   6   7   8   9
位置    0   0   0   3↓ 4   5   5   6   7   8
----------------------------------------------
                   ●
索引    0   1   2   3   4   5   6   7   8
数值    9   8   3   3   9   2   4   6   3
----------------------------------------------
       ○      ○  ○  ○  ○          ○
索引    0   1   2   3   4   5   6   7   8
数值    2   ?   3   3   4   6   ?   ?   9

                   ●
数值    0   1   2   3   4   5   6   7   8   9
位置    0   0   0   2↓ 4   5   5   6   7   8
----------------------------------------------
               ●
索引    0   1   2   3   4   5   6   7   8
数值    9   8   3   3   9   2   4   6   3
----------------------------------------------
       ○  ○  ○  ○  ○  ○          ○
索引    0   1   2   3   4   5   6   7   8
数值    2   3   3   3   4   6   ?   ?   9

                                       ●
数值    0   1   2   3   4   5   6   7   8   9
位置    0   0   0   1   4   5   5   6   7↓ 8
----------------------------------------------
           ●
索引    0   1   2   3   4   5   6   7   8
数值    9   8   3   3   9   2   4   6   3
----------------------------------------------
       ○  ○  ○  ○  ○  ○  ○      ○
索引    0   1   2   3   4   5   6   7   8
数值    2   3   3   3   4   6   8   ?   9

                                           ●
数值    0   1   2   3   4   5   6   7   8   9
位置    0   0   0   1   4   5   5   6   6   8↓
----------------------------------------------
       ●
索引    0   1   2   3   4   5   6   7   8
数值    9   8   3   3   9   2   4   6   3
----------------------------------------------
       ○  ○  ○  ○  ○  ○  ○  ○  ○
索引    0   1   2   3   4   5   6   7   8
数值    2   3   3   3   4   6   8   9   9

依位置信息放入新数组

计数排序法的程序实作

第一种计数排序法(不稳定)的程序实作方式如下:

第二种计数排序法(稳定)的程序实作方式如下:

计数排序法的复杂度

以 #{{n}}# 来表示要排序的数据笔数。以 #{{k}}# 来表示要排序的数据可能的值的数量。

项目 值 备注
最差时间复杂度 #{{O(n + k)}}#
最佳时间复杂度 #{{O(n + k)}}#
平均时间复杂度 #{{O(n + k)}}#
最差空间复杂度 #{{O(k)}}#
#{{O(n + k)}}#
第一种计数排序法(原地不稳定)。
第二种计数排序法(稳定)。
是否稳定 否
是
第一种计数排序法(原地不稳定)。
第二种计数排序法(稳定)。