十大排序算法——计数排序

一. 计数排序介绍

• 计数排序(Counting sort)是一种稳定的排序算法。计数排序使用一个额外的数组C，其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置。它只能对整数进行排序。
  

算法分析

• 当输入的元素是n 个0到k之间的整数时，它的运行时间是 O(n + k)。计数排序不是比较排序，排序的速度快于任何比较排序算法。

• 由于用来计数的数组C的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上1），这使得计数排序对于数据范围很大的数组，需要大量时间和内存。

• 最佳情况：T(n) = O(n+k) 最差情况：T(n) = O(n+k) 平均情况：T(n) = O(n+k)

二. 计数排序基础版

• 假设我们有一个数列arr=[3,4,6,4,8,1] 假设max为数列的最大值,此时我们创建一个大小为max+1的辅助数组sortArr,我们以此遍历arr数组,并将数列中的数对应辅助数组sortArr下标的值+1。

• 那么辅助数组中的数,就是其下标在待排序数组中出现的次数,最后我们通过遍历辅助数组sortArr就能获得一个排序好的序列。

 public static int[] countSort01(int[] arr) {
        // 获取序列的最大值
        int max = arr[0];
        int min = arr[0];
        for (int i = 0; i < arr.length; i++) {
            max = Math.max(max, arr[i]);
            min = Math.min(min, arr[i]);
        }
        // 创建一个长度为max+1的辅助数组 用来存储与辅助数组对应下标的数值 在待排序数列中出现的次数
        int[] sortArr = new int[max -min+ 1];
        for (int i = 0; i < arr.length; i++) {
            // 遍历带排序数列 每次将辅助序列对应下标处的数值+1
            sortArr[arr[i]]++;
        }
        int[] res = new int[arr.length];
        int index=0;
        for (int i = 0; i < sortArr.length; i++) {
            for (int j = 0; j < sortArr[i]; j++) {
                res[index++]=i;
            }
        }
        return res;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

三. 计数排序改进版

• 从上面看,我们已经能对一个数组进行基本的排序了,但是仔细想想,此时打印的排序的数是不稳定的,甚至于这个数与原数列失去的联系,它仅仅只是表示辅助数列的一个下标值

    public static int[] countSort02(int[] arr) {
        // 获取待排序数列的最大值 用来创建辅助数组
        int max = arr[0];
        for (int i = 0; i < arr.length; i++) {
            max = Math.max(max, arr[i]);
        }
        // 创建辅助数组 先在辅助数组存储其对应下标在待排序数中出现的次数 (与countSort01同)
        int[] sortArr = new int[max + 1];
        for (int i = 0; i < arr.length; i++) {
            sortArr[arr[i]]++;
        }
        // 对辅助数组进行改进 将其存储的对应待排序数列的次数 转换为临时排序数列的下标位置
        for (int i = 1; i < sortArr.length; i++) {
            sortArr[i] += sortArr[i - 1];
        }
        // 创建临时排序数列 并从右往左遍历arr将其顺序放于tsortArr
        int[] tsortArr = new int[arr.length];
        for (int i = arr.length - 1; i > 0; i--) {
            tsortArr[--sortArr[arr[i]]] = arr[i];
        }
        return tsortArr;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

四. 优化最终版本_空间节省

• 因为算法创建了两个0-(max+1)的数组进行辅助,如果是象[2,1,4,5,8]这样的数列自然没有问题,但如果是对像[99,97,96,99,100]这样的数列进行排序 就会造成比较大的空间浪费了,所以我们只需要生成max-min+1长的辅助数组就ok啦

 public static void main(String[] args) {
        int[] arr = new int[]{2, 5, 3, 0, 2, 3, 0, 3};
        System.out.println("排序前---------------------");
        System.out.println(Arrays.toString(arr));
        int[] res = countSort(arr);
        System.out.println("排序后---------------------");
        System.out.println(Arrays.toString(res));
    }


    public static int[] countSort(int[] arr) {
        // 获取待排序数列的最大值,与最小值 用来创建辅助数组
        int min = arr[0], max = arr[0];
        for (int i = 0; i < arr.length; i++) {
            max = Math.max(max, arr[i]);
            min = Math.min(min, arr[i]);
        }
        // 创建辅助数组 先在辅助数组存储其对应下标在待排序数中出现的次数 (与countSort01同)
        int[] sortArr = new int[max + 1];
        sortArr = new int[max - min + 1];
        for (int i = 0; i < arr.length; i++) {
            sortArr[arr[i] - min]++;
        }
        // 对辅助数组进行改进 将其存储的对应待排序数列的次数 转换为临时排序数列的下标位置
        for (int i = 1; i < sortArr.length; i++) {
            sortArr[i] += sortArr[i - 1];
        }
        // 创建临时排序数列
        int[] tsortArr = new int[arr.length];
        for (int i = arr.length - 1; i > 0; i--) {
            tsortArr[--sortArr[arr[i] - min]] = arr[i];
        }
        return tsortArr;
    }

    public static int[] countSort02(int[] arr) {
        // 获取待排序数列的最大值 用来创建辅助数组
        int max = arr[0];
        for (int i = 0; i < arr.length; i++) {
            max = Math.max(max, arr[i]);
        }
        // 创建辅助数组 先在辅助数组存储其对应下标在待排序数中出现的次数 (与countSort01同)
        int[] sortArr = new int[max + 1];
        for (int i = 0; i < arr.length; i++) {
            sortArr[arr[i]]++;
        }
        // 对辅助数组进行改进 将其存储的对应待排序数列的次数 转换为临时排序数列的下标位置
        for (int i = 1; i < sortArr.length; i++) {
            sortArr[i] += sortArr[i - 1];
        }
        // 创建临时排序数列 并从右往左遍历arr将其顺序放于tsortArr
        int[] tsortArr = new int[arr.length];
        for (int i = arr.length - 1; i > 0; i--) {
            tsortArr[--sortArr[arr[i]]] = arr[i];
        }
        return tsortArr;
    }
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
56
57