排序算法——计数排序详解_计数排序的时间复杂度

在排序的最终结果中，各元素的次序依赖于它们之间的比较。这类排序算法被称为比较排序。对于包含 $n$ 个元素的输入序列来说，任何比较排序算法在最坏情况下都要经过至少 $O(nlogn)$ 次比较。

而一些排序算法是用运算而不是比较来确定排序顺序的，如计数排序、基数排序以及桶排序。因此，比较次数的下界 $O(nlogn)$ 对它们是不适用的。

下面介绍计数排序。

计数排序

计数排序假设 $n$ 个输入元素中的每一个都是在 $0$ 到 $k$ 区间内的一个整数，其中 $k$ 为某个整数。计数排序的时间复杂度为 $O(n+k)$，当 $k=O(n)$ 时，排序的时间复杂度为 $O(n)$。

计数排序要求输入数据必须是整数，在实际工作中，当 $k=O(n)$ 时，一般会采用计数排序。如果输入元素的范围不在 $0$ 到 $k$ 之内，那么可以根据元素的最大值和最小值将其映射到 $0$ 到 $k$ 之内。

计数排序的基本思想：对于每一个输入元素 $x$，确定小于 $x$ 的元素个数。利用这一信息，就可以直接把 $x$ 放到它在输出数组中的位置上了。例如，如果有 17 个元素小于 $x$， 则 $x$ 就应该在第 18 个输出位置上。当有几个元素相同时，这一方案要略做修改，因为不能把他们放在同一个输出位置上。

算法执行过程中需要三个数组：
（1）数组 $A$，为要排序的输入数组，数组大小为 $n$。
（2）数组 $B$，提供临时存储空间，用于存储小于该下标值的元素个数，数组大小为 $k+1$。
（3）数组 $C$，存放排序的输出，数组大小为 $n$。
因此该算法的空间复杂度为 $O(n+k)$，当 $k=O(n)$ 时，空间复杂度为 $O(n)$。

算法执行过程如下：
（1）根据待排序数组 $A$ 中元素的最大值 $max$ 和最小值 $min$，申请大小为 $max-min+1$ 的数组 $C$。
（2）扫描数组 $A$，记录每个不同的元素出现的次数，将其记录在数组 $C$ 中。数组 $C$ 的每一位 $C[i]$ 就代表数组 $A$ 中元素 $i+min$ 出现的次数。可以发现，计数排序的该过程，其实就是将待排序集合 $A$ 中的每个元素值本身大小作为下标，依次进行了存放。而此时的数组 $C$ 就是为了确定每个元素值出现了几次。
（3）对数组 $C$ 中的每个值从前向后进行累加，每个位置的值更新为加上前一个位置的值，此时数组 $C$ 中每个元素 $C[i]$ 表示待排序数组 $A$ 中 小于等于该下标值 $i$ 的元素个数。
（4）反向遍历待排序数组 $A$ 来填充目标数组 $B$：将 $A$ 中每个元素值 $A[j]$ 放在新数组的第 $C[A[j]-min]$ 位，然后将 $C[A[j]-min]$ 减一。

用上图举例在输入数组 $A$ 上的处理过程。其中 $A$ 中的每一个元素都是在 $0$ 到 $5$ 范围内：
（a）首先扫描一遍数组 $A$，记录 $A$ 中每个元素出现的次数，将该信息存储在数组 $C$ 中， $C$ 中每个下标就表示 $A$ 中不同的元素值。如当前图中数组 $C$ 所示；
（b）从前向后对计数进行累加，当前数组 $C$ 中每个元素代表小于等于该下标的元素出现的次数；
（c~e）反向遍历输入数组 $A$，将其每个元素 $A[j]$ 放在输出数组 $B$ 的第 $C[A[j]]$ 项，然后将 $C[A[j]]$ 减一。图中表示该过程迭代了一次、两次和三次之后，输出数组 $B$ 和辅助数组 $C$ 的情况。其中数组 $B$ 只有浅色阴影部分有元素值填充；
（f）最终排好序的输出数组 $B$。

计数排序的一个重要性质就是它是稳定的：具有相同值的元素在输出数组中的相对次序相同。也就是说，对两个相同的数来说，在输入数组中先出现的数，在输出数组中在位于前面。
计数排序的稳定性很重要的另一个原因是：计数排序经常会被用作计数排序算法的一个子过程。

虽然计数排序看上去很强大，但是它存在两大局限性：

• 当数据最大值和最小值差距过大时，并不适用于计数排序。

  比如给定 20 个随机整数，范围在 0 到 1 亿之间，此时如果使用计数排序的话，就需要创建长度为 1 亿的数组，不但严重浪费了空间，而且时间复杂度也随之升高。
  因此计数排序只适用于元素值较为集中的情况。

• 当数列元素不是整数时，并不适用于计数排序。

  如果数列中的元素都是小数，比如 3.1415，或是 0.00000001 这样子，则无法创建对应的统计数组，这样显然无法进行计数排序。

正是由于这两大局限性，才使得计数排序不像快速排序、归并排序那样被人们广泛适用。

Counting-sort(A, B) {
    maximum = max(A);
    minimum = min(A);
    int k = maximum - minimum + 1;

    let C[0..k] be a new array
    // initialion
    for i=0 to k            
        C[i] = 0;

    for j=0 to A.length - 1
        C[A[j]-minimum]++;
    // C[i] now contains the number of elements equal to i.

    for i=1 to k
        C[i] = C[i] + C[i-1]
    // C[i] now contains the number of elements less than or equal to i. 

    for j = A.length-1 downto 0
        B[C[A[j]-minimum]] = A[j];
        C[A[j]-minimum]--;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23