• home > theory > algorithm > Sorting >

    再谈计数排序—看了多篇文件理解记忆总结—排序算法

    Author:zhoulujun Date:

    计数排序,按照百度百科和维基百科和一些教科书的讲解,不甚明了。好的讲解方法,一看一目了然。这里是我自己看的几篇文章结合自己的感悟拼凑出来的笔记。希望本篇对算法过程和算法过程的讲解有助于你理解记忆

    计数排序概念

    计数排序是一个非基于比较的排序算法,该算法于1954年由 Harold H. Seward 提出。

    元素从未排序状态变为已排序状态的过程,是由额外空间的辅助和元素本身的值决定的。计数排序过程中不存在元素之间的比较和交换操作,根据元素本身的值,将每个元素出现的次数记录到辅助空间后,通过对辅助空间内数据的计算,即可确定每一个元素最终的位置。当然这是一种牺牲空间换取时间的做法,它的优势在于在对一定范围内的整数排序时,它的复杂度为Ο(n+k)(其中k是整数的范围),快于任何比较排序算法。 [而且当O(k)>O(n*log(n))的时候其效率反而不如基于比较的排序(基于比较的排序的时间复杂度在理论上的下限是O(n*log(n)), 如归并排序,堆排序)。

    比较性质排序算法的时间复杂度有一个理论边界,即O(N㏒₂N),N 个元素的序列,能够形成的所有排列个数为 N!,即该序列构成的决策树叶子节点个数为 N!,由叶子节点个数可知,决策树的高度为 log_2(N!),即由决策树根节点到叶子节点的比较次数为 log_2(N!),由斯特灵公式,n!≈(2nπ)^½(n/3)^n,转换可得,比较性质的算法复杂度理论边界为 O(Nlog_2N) 。

    计数排序特点

    • 非比较排序

    • 桶思想的一种

    适用场景

    量大但是范围小

    • 某大型企业数万员工的年龄排序      范围(0--100)

    • 如何快速得知高考名次(腾讯面试题) 范围(0--750)

    算法过程

    1. 根据待排序集合中最大元素和最小元素的差值范围,申请额外空间

      花 O(n)的时间扫描一下整个序列 A,获取最小值min和最大值max,开辟一块新的空间创建新的数组B,长度为 max - min + 1(因为申请的额外空间足以将 min 和 max 之间的所有元素记录,将待排序集合中每一个元素都记录到额外空间上)

    2. 遍历待排序集合,将每一个元素出现的次数记录到元素值对应的额外空间内;

      组 B 中 index 的元素记录的值是 A 中某元素出现的次数

    3. 对额外空间内数据进行计算,得出每一个元素的正确位置;

    4. 将待排序集合每一个元素移动到计算得出的正确位置上。


    算法流程解释

    与比较排序注重于元素之间的比较不同,计数排序专注于找准自己的位置,而不关心自己比谁小,比谁大。其核心在于,对于任意一个属于数组array的元素number,统计其在array内出现的次数,将其以键值对的形式保存在hash,如果hash没有number,使hash[nmber] = 1,并且与max做对比是否需要重置max(max是hash的最大键,也可以理解为共有多少的桶。。),否则hash[number]++,形成hash后,将其按顺序push到新数组newArr。

    20200127215936484101591.jpg

    计数排序实例:

    先假设20个随机整数的值是:9, 3, 5, 4, 9, 1, 2, 7, 8,1,3, 6, 5, 3, 4, 0, 10, 9, 7, 9

    1. 取数组的最大值max=9,min=0,可得申请额外空间大小为:max - min +1 =10

    2. 遍历排序,记录每个元素在相应位置的出现次数,比如第一个整数是9,那么数组下标为9的元素加1,第二个整数是3,那么数组下标为3的元素加1,最终,数列遍历完毕时,数组的状态如下:

      计数排序举例

    3. 有了这个统计结果,排序就很简单了,直接遍历数组,输出数组元素的下标值,元素的值是几,就输出几次:

    再看一个案列:

    计数排序案列

    计数排序代码示范案列

    下面是直接按照上面的步骤,js实现code

    /**
     * 计数排序算法
     * @param arr {Array} 待排序数组
     * @param min {Number|undefined} 数组中的最小值
     * @param max {Number|undefined} 数组中的最小值
     * @return {Array} 排序完的数组
     */
    function countSort (arr, min, max) {
        if (!Array.isArray(arr)) {
            return arr
        }
        let length = arr.length
        if (length < 2) {
            return arr
        }
        // 如果不知道最大值与最小值,扫描数组,取出数组中的最大值与最小值
        if (!min || !max) {
            min = arr[0]
            max = arr[0]
            for (let i = 1; i < length; i++) {
                if (min > arr[i]) {
                    min = arr[i]
                }
                if (max < arr[i]) {
                    max = arr[i]
                }
            }
        }
        // 开辟一块 max - min + 1的空间(数组),
        let tempArr = new Array(max - min + 1).fill(0)
        // 记录每个元素在相应位置的出现次数
        for (let i = 0; i < length; i++) {
            if (arr[i] !== undefined) {
                tempArr[arr[i]] += 1
            }
        }
        // 将待排序集合每一个元素移动到计算得出的正确位置上
        let reArr = []
        for (let i = 0; i < tempArr.length; i++) {
            let value = tempArr[i]
            if (value !== 0) {
                reArr = reArr.concat(new Array(value).fill(i))
            }
        }
        return reArr
    
    }

    这个算法,这也写,觉得好理解些,但是,比如负数,排序就无法搞。

    /**
     * 计数排序算法
     * @param arr {Array} 待排序数组
     * @return {Array} 排序完的数组
     */
    function countSort2 (arr) {
        let hashMap = {}
        if (!Array.isArray(arr)) {
            return arr
        }
        let length = arr.length
        if (length < 2) {
            return arr
        }
        let min = arr[0]
        let max = arr[0]
        for (let i = 0; i < length; i++) {
            let num = arr[i]
            if (hashMap[num] === undefined) {
                hashMap[num] = 1
            } else {
                hashMap[num]++
            }
            if (i === 0) {
                continue
            }
            if (num > max) {
                max = num
            }
            if (num < min) {
                min = num
            }
        }
        let reArr = []
        for (let hashIndex = min; hashIndex < max + 1; hashIndex++) {
            let repeatTimes = hashMap[hashIndex]
            if (repeatTimes !== undefined) {
                reArr = reArr.concat(new Array(repeatTimes).fill(hashIndex))
            }
        }
        return reArr
    
    }

    计数排序测试

    let testArr = [10, 7, 1, 0, 100, 4, 5, 2, 70]
    console.log(countSort(Object.assign([], testArr)))
    console.log(countSort2(Object.assign([], testArr)))


    参考文章:

    排序算法(八):计数排序 https://www.jianshu.com/p/86c2375246d7

    什么是计数排序? https://www.cnblogs.com/kyoner/p/10604781.html

    五分钟学会一个有意思的排序:计数排序 https://www.v2ex.com/t/511806

    排序算法入门(三) 计数排序,桶排序 https://zhuanlan.zhihu.com/p/46877267

    https://baike.baidu.com/item/计数排序/8518144?fr=aladdin



    转载本站文章《再谈计数排序—看了多篇文件理解记忆总结—排序算法》,
    请注明出处:https://www.zhoulujun.cn/html/theory/algorithm/SortingAlgorithms/8263.html