什么是计数排序?

计数排序、基数排序、桶排序,这几种排序算法,可能大家见到的这次不多,有些大学的教材课本中,甚至有些都没有计数排序算法。

所以呢,帅地今天就简单讲一讲计数排序算法吧,而不会像前面一样长篇大论,因为我觉得,每一个学习计数排序的,应该都是有一定的算法基础了,而对于计数排序,我觉得大家掌握最基本的思想就可以了,平时做算法题的时候,还是会偶尔用到。

当然,计数排序如果要深入讲解,其实也是可以比较复杂的,但是这里,帅地只讲最简洁的,因为我觉得了解了基础的,就差不多了。

举个例子,假如我要给如下这个数组排序,你会如何排序呢?

输入 arr[] = {9,3,5,4,9,1,2,7,8,1,3,6,5,3,4,0,10,9 ,7,9}。

如果用快速排序,归并排序等这些排序算法的话,那么他们的时间复杂度其实是 O(nlogn)。

那么有没有一种方法,使得它的时间复杂度是 O(n) 呢?

答是有的,那便是计数排序

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

例如对于上面那个例子,我们可以创建一个数组大小为 11 的临时数组 temp

图片

因为数组的最大值是 10,所以临时数组的最大下标为 10 即可。

然后遍历数组,第一个整数是9,那么数组下标为9的元素加1:

图片

第二个整数是3,那么数组下标为3的元素加1:

图片

最终,数列遍历完毕时,数组的状态如下:

图片

之后我们只需要遍历临时数组 temp,输出临时数组元素的下标值即可,元素的值是几,就输出几次,结果如下:

0,1,1,2,3,3,3,4,4,5,5,6,7,7,8,9,9,9,9,10

显然,这个输出的数列已经是有序的了。

Java 代码如下(代码会做详细的注释)

   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 + 1的临时数组
        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++) {
            // temp[i] 的值表示元素 i 出现的次数
            for (int j = temp[i]; j > 0; j--) {
                arr[k++] = i;
            }
        }
        return arr;
    }

优化一下

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

也就是说,我们创建的临时数组大小 (max – min + 1)就可以了,然后我们再把 min作为偏移量。优化之后的代码如下所示:

    public static int[] sort(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;
        //创建大小为max的临时数组
        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++) {
          // temp[i] 的值表示元素 i 出现的次数
            for (int j = temp[i]; j > 0; j--) {
                arr[k++] = i + min;
            }
        }
        return arr;
    }

我这里还给大家准备了一个动画,大家看看就好

image-20230213174646813

有人可能会问,如果数组只有十个元素,最小值为 min = 0,最大值 max = 1000000。那我不是得创建一个 大小为 1000000 的数组?

或者说,如果我数组中有浮点数,那不就是无法作为下标来使用了?

别问,问就是,每一种排序算法都有它的局限性,不然还用啥快速排序,目前用的最广的感觉还是快速排序,想计数排序这种,适用特定领域数据下的排序,例如最大值和最小值的差值不是很大的整数数组。

发表回复

后才能评论