4. 其他非基于比较排序（了解）

1. 计数排序（附有自己的视频讲解）

计数排序

    /**
     * 时间复杂度：O(N+范围)
     * 空间复杂度：O(范围)
     * 稳定性：
     * 计数排序：适合 给定一个范围的数据 进行排序
     * @param array
     */
    public static void countSort(int[] array) {
        int maxVal = array[0];
        int minVal = array[0];

        for (int i = 0; i < array.length; i++) {
            if(array[i] < minVal) {
                minVal = array[i];
            }
            if(array[i] > maxVal) {
                maxVal = array[i];
            }
        }
        //就能确定当前数组的最大值 和 最小值
        int len = maxVal - minVal + 1;
        int[] count = new int[len];
        //开始遍历array数组 进行计数
        for (int i = 0; i < array.length; i++) {
            int val = array[i];
            count[val-minVal]++;

        }

        int index = 0;//array数组的下标
        for (int i = 0; i < count.length; i++) {
            //确保 当前count数组 可以检查完
            while (count[i] != 0) {
                array[index] = i+minVal;
                index++;
                count[i]--;
            }
        }
    }
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

思想：计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。 操作步骤

1. 统计相同元素出现次数
2. 根据统计的结果将序列回收到原来的序列中

【计数排序的特性总结】

1. 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。
2. 时间复杂度：O(MAX(N,范围))
3. 空间复杂度：O(范围)
4. 稳定性：稳定

2. 基数排序（附有自己的视频讲解）

基数排序

3. 桶排序（附有自己的视频讲解）

桶排序