文章

计数排序

计数排序(Counting sort)是一种稳定的线性时间排序算法。该算法于1954年由[哈罗德·H·西华德]提出。计数排序使用一个额外的数组𝐶,其中第i个元素是待排序数组𝐴中值等于𝑖的元素的个数。然后根据数组𝐶来将𝐴中的元素排到正确的位置。

计数排序

计数排序(Counting Sort)是一种线性时间复杂度的排序算法。它适用于排序一定范围内的整数,特别是当范围不大时,表现非常高效。

计数排序的原理

计数排序的主要思想是通过统计每个元素的出现次数,计算出每个元素在排序后数组中的位置,从而实现排序。计数排序适用于数据范围相对较小且数据分布比较均匀的情况。

图示

计数排序

计数排序

计数排序的步骤

  1. 找出数组中的最大值和最小值:确定数据的范围。
  2. 创建计数数组:计数数组的大小为最大值和最小值之间的差加1,用于记录每个元素的出现次数。
  3. 统计每个元素的出现次数:遍历待排序数组,填充计数数组。
  4. 计算元素的最终位置:对计数数组进行累加处理,得到每个元素在排序后数组中的位置。前缀和具有明确的意义,prefix[num] - 1 代表元素 num 在结果数组 res 中最后一次出现的索引。这个信息非常关键,因为它告诉我们各个元素应该出现在结果数组的哪个位置。
  5. 构建输出数组:根据计数数组的信息,将原数组的元素放到正确的位置上。
  6. 复制到原数组:将输出数组复制回原数组,完成排序。

计数排序示例

step1

step1

step2

step2

step3

step3

step4

step4

step5

step5

step6

step6

step7

step7

step8

step8

复杂度分析

当输入的元素是𝑛个0到𝑘之间的整数时,它的运行时间是 $\Theta (n+k)$。计数排序不是比较排序,因此不被 $\Omega (n\log n)$的下界限制。

  • 时间复杂度为 $O(n + k)$、非自适应排序 :涉及遍历 nums 和遍历 counte ,都使用线性时间。一般情况下 $n \gg k$ ,时间复杂度趋于 $O(n)$ 。
  • 空间复杂度为 $O(n + k)$、非原地排序:借助了长度分别为 $n$ 和 $m$ 的数组 rescounte
  • 稳定排序:由于向 res 中填充元素的顺序是“从右向左”的,因此倒序遍历 nums 可以避免改变相等元素之间的相对位置,从而实现稳定排序。实际上,正序遍历 nums 也可以得到正确的排序结果,但结果是非稳定的。

时间复杂度

  • 最佳情况:$O(n+k)$。
  • 最坏情况:$O(n+k)$。
  • 平均情况:$O(n+k)$。

空间复杂度

  • 空间复杂度:$O(n+k)$。

局限性

计数排序非常巧妙,仅通过统计数量就可以实现高效的排序。然而,使用计数排序的前置条件相对较为严格。

计数排序只适用于非负整数。若想将其用于其他类型的数据,需要确保这些数据可以转换为非负整数,并且在转换过程中不能改变各个元素之间的相对大小关系。例如,对于包含负数的整数数组,可以先给所有数字加上一个常数,将全部数字转化为正数,排序完成后再转换回去。

计数排序适用于数据量大但数据范围较小的情况。比如,在上述示例中 $k$ 不能太大,否则会占用过多空间。而当 $n \ll k$ 时,计数排序使用 $O(k)$ 时间,可能比 $O(n \log n)$ 的排序算法还要慢。

Java代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
import java.util.Arrays;

public class CountingSort {

    public static void countingSort(int[] nums) {
        int n = nums.length;

        // 找出数组中的最大值和最小值
        int max = Arrays.stream(nums).max().getAsInt();
        int min = Arrays.stream(nums).min().getAsInt();

        // 创建计数数组,大小为 (max - min + 1)
        int range = max - min + 1;
        // counter[num] 代表 num 的出现次数
        int[] counter = new int[range];
        // 初始化数组 res 用于记录结果
        int[] res = new int[n];

        // 统计每个元素的出现次数
        for (int num : nums) {
            counter[num - min]++;
        }

        // 计算元素的最终位置(累加处理)
        // 求 counter 的前缀和,将“出现次数”转换为“尾索引”
        // 即 counter[num]-1 是 num 在 res 中最后一次出现的索引
        for (int i = 1; i < counter.length; i++) {
            counter[i] += counter[i - 1];
        }
		
        // 倒序遍历 arr ,将各元素填入结果数组 res 
        for (int i = n - 1; i >= 0; i--) {
	        int num = nums[i] - min; 
	        // 将 num 放置到对应索引处 
	        res[counter[num] - 1] = num;
	        // 令前缀和自减 1 ,得到下次放置 num 的索引 
	        counter[num]--; 
        }

        // 将输出数组复制回原数组
        System.arraycopy(res, 0, nums, 0, n);
    }

    public static void main(String[] args) {
        int[] arr = {4, 2, 2, 8, 3, 3, 1};
        System.out.println("Given Array:");
        System.out.println(Arrays.toString(arr));

        // 调用计数排序函数
        countingSort(arr);

        System.out.println("Sorted Array:");
        System.out.println(Arrays.toString(arr));
    }
}
本文由作者按照 CC BY 4.0 进行授权