深入浅出排序算法之计数排序

简介: 深入浅出排序算法之计数排序

1. 原理

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

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

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

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

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

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 + " ");
        }
    }

3. 性能分析

时间复杂度 空间复杂度
O(MAN(N,范围)) O(N)
对数据的范围敏感 对数据的范围敏感
相关文章
|
算法 搜索推荐 Python
Python算法——计数排序
Python算法——计数排序
78 0
|
2月前
|
搜索推荐 Java Go
深入了解计数排序算法
深入了解计数排序算法
39 4
|
6月前
|
算法 搜索推荐
数据结构算法--6 希尔排序和计数排序
**希尔排序**是插入排序的改进版,通过分组插入来提高效率。它逐步减少元素间的间隔(增量序列),每次对每个间隔内的元素进行插入排序,最终增量为1时进行最后一次直接插入排序,实现整体接近有序到完全有序的过程。例如,对数组`5, 7, 4, 6, 3, 1, 2, 9, 8`,先以间隔`d=4`排序,然后`d=2`,最后`d=1`,完成排序。计数排序则适用于0到100的数值,通过统计每个数出现次数,创建对应计数数组,再根据计数重建有序数组,时间复杂度为`O(n)`。
|
5月前
|
存储 算法 搜索推荐
|
算法 搜索推荐 大数据
【算法】排序——归并排序和计数排序
上两篇文章讲解了插入排序、选择排序以及交换排序,每种类型的排序大类下都有一到两种排序,今天给大家带来的是归并排序,和前面几种排序一样都属于比较排序中的一种,是通过比较数组中的元素来实现排序的,还给大家带来一种非比较排序计数排序,让我们开始今天的排序之吧!!!
|
6月前
|
搜索推荐 算法
【C/排序算法】:归并排序和计数排序
【C/排序算法】:归并排序和计数排序
40 0
|
7月前
|
存储 算法 前端开发
前端算法之计数排序
前端算法之计数排序
36 1
|
7月前
|
存储 搜索推荐 算法
【数据结构】八大排序之计数排序算法
【数据结构】八大排序之计数排序算法
47 4
|
7月前
|
搜索推荐 C语言
【C语言/数据结构】排序(归并排序|计数排序|排序算法复杂度)
【C语言/数据结构】排序(归并排序|计数排序|排序算法复杂度)
43 0
|
7月前
|
搜索推荐
排序算法之八:计数排序
排序算法之八:计数排序
排序算法之八:计数排序