前言

从复杂度较高的，冒泡排序，选择排序，插入排序（不包含二分插入排序） ，这些时间复杂度为 O(N^2) 的排序，再到归并排序，快速排序，堆排序，这些时间复杂度为 O(nlogn)的排序，还有么有更快的？
答有！它来了它来了，它带着一波动画共计160帧画面走来了！问它为啥160帧，只因我是一帧一帧改的…奥利给 熬夜脱发又又一次。

计数排序

计数排序是一种，不用比较元素间大小的 高效排序，原因是它采用，关联数组元素下标的方式关联，因为元素的索引下标天然就是有序的。
例如： 待排序数组 { 3, 7, 5}
找出 元素最大值，然后建一个可以包含 3~7 区间的数组，对应索引值 ，存入，那此时的数组只要从头遍历出来即可

注意： 上图 索引 0 ，1， 2 都白白浪费了 ，因为数组最小元素是3，所以这里有优化空间，后面的代码会有体现的。

动漫

核心代码

   @Test
    public void counrtSort () {
        int[] arr = {2, 11, 1, 8, 7, 18, 18, 6, 5, 3, 20, 4};
        System.out.println(Arrays.toString(arr));
        int max = arr[0];
        int min = arr[0];
        // 选出最大值与最小值，找出被排序元素的区间
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            } else if (arr[i] < min) {
                min = arr[i];
            }
        }
        // 建立 min~~~至 max的 区间，并关联索引位置，成为计数数组
        int[] counrtArr = new int[max - min + 1];
        for (int i = 0; i < arr.length; i++) {
            counrtArr[arr[i] - min]++;
        }

        // 把计数数组变形，变成一个排名数组
        for (int i = 1; i < counrtArr.length; i++) {
            counrtArr[i] += counrtArr[i - 1];
        }
        int[] rs = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            rs[counrtArr[arr[i] - min] - 1] = arr[i];
            counrtArr[arr[i] - min]--;
        }
        System.out.println(Arrays.toString(rs));
    }

复杂度

• 遍历找出最大值最小值 ，N次。
• min~~~至 max的 区间，并关联索引位置，N次。
• 遍历计数数组，max - min + 1次，设为K次。
• 把计数数组变形，变成一个排名数组 ，遍历K次。
• 最终遍历源数组，N次。

结果： 3N+2K
去常数项，最终结果：
N+K

优缺点

• 优点：
  时间复杂度相比较于传统比较大小排序，更快
• 缺点：
  1 当数组最大值和最小值差距过大时，不适合排序
  2 当数组元素不是整数，不适合排序

对于次局限性，桶排序算法作出了弥补。 桶排序传送门：
桶排序图解与代码

赠人玫瑰，手有余香，你的点赞，备受鼓舞！

如果你能看到这里了，不如点赞关注一波，我会认真分享每一篇博文。大家共同成长。

我的公众号：茄子的笔记

更多分享可见：

在这里插入图片描述：