计数排序

我们之前学习过了快速排序和归并排序等排序算法,特别是在平时的应用中,这两种排序算法的使用都很广泛。

但是我们注意到这两种排序算法的时间复杂度都是 {O(NlogN)} ,我们想有没有一种排序算法的时间复杂度能够达到 {O(N)} 呢?

其实是有的,就是我们要学习的计数排序。

计数排序思想介绍

计数排序在排序的过程中,会统计相同元素出现的次数,并将其记录到统计数组中,从而实现有序。

举个例子,假设待排序数组的元素大小范围都是 [0, 10],那么我们可以创建一个大小为 11 ,数组元素初始值都为 0 的统计数组,

在遍历排序数组中的过程中,如果元素等于 8,那么统计数组下标为 8 的元素则 + 1

如下图所示:

完成统计之后,统计数组的结果如下图所示

计数排序算法的思想和代码都是比较简单的,我们重在理解,因为其思想我们在解决其他算法题的时候,也经常会用到。

代码实现

public class Solution {
    public int[] sort (int[] nums) {
        int[] cnt = new int[11];
        for (int i = 0; i < nums.length; i++) {
            cnt[nums[i]]++;
        }
        int j = 0;
        for (int i = 0; i < cnt.length; i++) {
            while (cnt[i]-- > 0) {
                nums[j++] = i;
            }
        }
        return nums;
    }
}

时间复杂度

计数排序的最大特点就是他只需要遍历排序数组一次进行计数即可,所以时间复杂度是 {O(N)}

空间复杂度

计数排序需要一个统计数组来辅助计数,统计数组的范围又与排序数组的元素的大小范围有关,如果大小范围不能确定,或者范围很大,那么这一点也是我们在选择排序算法需要慎重考虑的一点。

稳定性

因为计数排序的使用场景只适用于整数数字的排序,因此也不会对稳定性有什么要求了。

写在最后

总的来说,计数排序是一种优点和缺点都很明显的排序算法,优点是时间复杂度是 {O(N)},缺点是适应场景的局限以及空间复杂度的不确定性。

我们重在学习通过统计数组进行计数的思想,后面我们在讲具体的算法题的时候会经常用到。

好了,今天就讲到这里,希望大家在仅剩的假期里好好充电啊!

发表回复

后才能评论