深入浅出排序算法之计数排序-Toy模板网

这篇具有很好参考价值的文章主要介绍了深入浅出排序算法之计数排序。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1. 原理

2. 代码实现

3. 性能分析

1. 原理

首先看一个题目，有n个数，取值范围是 0~n，写出一个排序算法，要求时间复杂度和空间复杂度都是O(n)的。

为了达到这种效果，这一篇将会介绍一种不基于比较的排序方法。这种方法被称为计数排序。

计数排序的思路是这样的，对于每一个待排序元素a，如果知道了待排序数组中有多少个比它小的数，那么就可以直接知道在排序后的数组中 a 应该在什么位置上。比如，如果一个数组中有3个数是比a小的，那么，在排序后的数组里，a必然会出现在第4位。

现在问题转化成，对于待排序数组里的一个数，如何能快速知道比它小的数字有多少个。要解决这个问题，我们不能使用比较的办法，那样时间复杂度是无法降下来，只有换一个思路，以空间换时间。因为n个数的取值范围是 0~n，所以，不妨使用一个大小为 n 的数组来统计从0到n，每个数在待排序数组中出现的次数。这个数组类似于直方图数组，因为这种方式也被称做是基于统计的排序。直方图统计的思路简单清晰，在很多题目中都会有出现，一定要熟练掌握这种技巧。

深入浅出排序算法之计数排序,Java版本的算法题,Java数据结构,排序算法,算法,数据结构

强调：计数排序适合排序一组集中的数据。

2. 代码实现

    //计数排序
    public static void countSort(int[] array) {
        //1. 找到待排序数组的范围，也就是找到最大值和最小值
        int max = array[0];
        int min = array[0];
        //循环遍历找寻最小值和最大值
        for (int i = 1; i < array.length; i++) {
            if (array[i] > max)
                max = array[i];
            if (array[i] < min)
                min = array[i];
        }
        //计算待排数组的长度
        int len = max - min + 1;
        //2. 定义一个计数数组
        int[] count = new int[len];
        //3. 遍历array数组，把数据计数到计数数组中
        for (int i = 0; i < array.length; i++) {
            count[array[i] - min]++;
        }
        //4. 将array数组还原
        int index = 0;//来控制array数组的下标
        for (int i = 0; i < array.length; i++) {
            //这个循环的作用，是把count里面标记的数据取出来
            while (count[i] > 0) {
                array[index] = i + min;
                index++;
                count[i]--;
            }
        }
    }

        public static void main(String[] args) {
        int[] a = {5,4,3,2,1};
        Sort.countSort(a);
        for (int x : a) {
            System.out.print(x + " ");
        }
    }

深入浅出排序算法之计数排序,Java版本的算法题,Java数据结构,排序算法,算法,数据结构文章来源地址https://www.toymoban.com/news/detail-736822.html