计数排序

(Updated: )
排序算法

过程

就是把数组元素作为数组的下标，然后用一个临时数组统计该元素出现的次数，例如 temp[i] = m, 表示元素 i 一共出现了 m 次。最后再把临时数组统计的数据从小到大汇总起来，此时汇总起来是数据是有序的。

动图展示

代码实现

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
/**
 * 计数排序
 */

public class CountSort1 {

    public static int[] countSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return arr;
        }
        int n = arr.length;
        int max = arr[0];
        //寻找数组的最大值
        for (int i = 1; i < n; i++) {
            if (max < arr[i]) {
                max = arr[i];
            }
        }
        //创建大小为max的临时数组
        int[] temp = new int[max + 1];
        //统计元素i出现的次数
        for (int i = 0; i < n; i++) {
            temp[arr[i]]++;
        }
        int k = 0;
        //把临时数组统计好的数据汇总到原数组
        for (int i = 0; i <= max; i++) {
            for (int j = temp[i]; j > 0; j--) {
                arr[k++] = i;
            }
        }
        return arr;
    }

    public static void main(String[] args) {
        int[] arr = {2, 5, 3, 1, 4, 6};
        countSort(arr);
        System.out.println(Arrays.toString(arr));
    }

}

性质：

  1. 时间复杂度：O(n+k)
  2. 空间复杂度：O(k)
  3. 稳定排序
  4. 非原地排序

优化

上面的代码中，我们是根据 max 的大小来创建对应大小的数组，假如原数组只有10个元素，并且最小值为 min = 10000，最大值为 max = 10005，那我们创建 10005 + 1 大小的数组不是很吃亏，最大值与最小值的差值为 5，所以我们创建大小为6的临时数组就可以了。

也就是说，我们创建的临时数组大小 (max - min + 1)就可以了，然后在把 min作为偏移量。

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
/**
 * 计数排序优化
 */

public class CountSort2 {

    public static int[] countSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return arr;
        }
        int n = arr.length;
        int min = arr[0];
        int max = arr[0];
        //寻找数组的最大值和最小值
        for (int i = 1; i < n; i++) {
            if (max < arr[i]) {
                max = arr[i];
            }
            if (min > arr[i]) {
                min = arr[i];
            }
        }
        int d = max - min + 1;
        //创建大小为 d 的临时数组
        int[] temp = new int[d];
        //统计元素i出现的次数
        for (int i = 0; i < n; i++) {
            temp[arr[i] - min]++;
        }
        int k = 0;
        //把临时数组统计好的数据汇总到原数组
        for (int i = 0; i < d; i++) {
            for (int j = temp[arr[i]]; j > 0; j--) {
                arr[k++] = i + min;
            }
        }
        return arr;
    }

}

参考