数据结构之计数排序_数据结构 计数排序

1 计数排序

计数排序是一种比较快速的排序方法，相对于冒泡排序、快速排序、堆排序、鸡尾酒排序等，计数排序是一种不需要进行元素之间对比的排序算法，但是该算法也有一定的局限性。
算法思路：
需要使用一个计数数组，将待排序数组中的每个元素遍历一遍，将每个元素出现的个数放到计数数组中，元素的值是多少就在计数数组相应的下标元素上的计数加1。举例：

待排序数组：[2,4,3,2,2,2,5,5,6,2,9,8,8,9]
通过计算，可以知道当前数组的最大值是9，所以创建一个大小为9+1的数组，然后遍历该数组，并记录每个元素出现的次数,计数数组如下：
[0, 0, 5, 1, 1, 2, 1, 0, 2, 2]
然后，按顺序遍历该计数数组即可，数组中元素的值代表以该下标为值的元素在数组中出现的次数。结果如下：
升序排序：[2, 2, 2, 2, 2, 3, 4, 5, 5, 6, 8, 8, 8, 9]

2 朴素版计数排序代码

public class CountSort {
    private int[] array;

    public CountSort(int[] array) {
        this.array = array;
    }

    public void increaseSortOrigin(){
        int n = this.array.length;
        int max = this.array[0];
        for (int i = 1; i < n; i++) {
            if (this.array[i]>max)
                max=this.array[i];
        }
        int [] countArray = new int[max+1];
        for (int i = 0; i < n; i++) {
            countArray[this.array[i]] ++;
        }
        System.out.println(Arrays.toString(countArray));
        int c=0;
        for (int i = 0; i < max; i++) {
            for (int j = 0; j < countArray[i]; j++) {
                this.array[c] = i;
                c++;
            }
        }
    }
}
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

3 优化版计数排序

当待排序数组中的最大值很大时，那么可能会浪费很多空间，因为需要创建一个空间很大的计数数组来存放计数，且此时元素有不多的话，那浪费将更加严重。那么如何对其进行优化呢，可以使用一个最大和最小值，使用相对值来存放计数。

如下面的数组：
[92,94,93,92,92,92,95,95,96,92,99,98,98,99]，如果按照上面的思路可能需要一个数组空间为99的计数数组，但是元素的值主要集中在90-100之间，那么前面90个空间就浪费了。所以使用相对位置进行计数。让数组中每一个元素减去数组中的最小元素的值，当对计数数组进行还原时，再加上最小值进行还原。使用相对计数的话，可以看到计数数组的空间就小很多。

public class CountSort {
    private int[] array;

    public CountSort(int[] array) {
        this.array = array;
    }

    public void increaseSort(){
        int n = this.array.length;
        int max = this.array[0];
        int min = this.array[0];
        for (int i = 1; i < n; i++) {
            if (this.array[i] > max)
                max = this.array[i];
            if (this.array[i] < min)
                min= this.array[i];
        }
        int [] countArray = new int[max-min+1];
        for (int i = 0; i < n; i++) {
            countArray[this.array[i]-min] ++;
        }
        System.out.println(Arrays.toString(countArray));
        int c = 0;
        for (int i = 0; i < max-min+1; i++) {
            for (int j = 0; j < countArray[i]; j++) {
                this.array[c] = i+min;
                c++;
            }
        }
    }
}
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

4 算法复杂度分析

4.1 时间复杂度

由于计数排序使用使用一个计数数组进行缓冲，且计数数组的大小为max-min=m，原始数组的大小为n，从算法中可以看到，需要对原数组数据进行3次遍历，对计数数据进行1次遍历，所以空间复杂度为3n+m->O(n+m)

4.2 空间复杂度

如果不考虑原数组的大小的话，只考虑额外的开销，那么该算法的空间复杂度为O(m)。

5 算法局限性

• 计数排序由于没有元素之间的对比、需要用到数组下标来对元素进行排序，所以该算法只能针对非负浮点数进行排序。
• 该算法只能针对待排序数组中元素相差不大的情况，比如：一个数组中，最大值1亿、最小值为0、总共10个元素，那么就会有很多空间被浪费掉了。所以该算法不适用与该种情况。