排序-4-计数排序

我心飞翔 分类:javascript

快速排序、堆排序这样时间复杂度为O(nlogn)的算法已经很快了,但是事实上还存在更快的排序算法,在理想的情况下,某些算法甚至可以做到线性的时间复杂度,例如:计数排序、桶排序、基数排序

例如冒泡排序、堆排序、快速排序都是基于元素之间的比较来进行排序的,但是以计数排序来说,这种排序算法是基于元素的下标来确定元素位置的

初识计数排序

假设数组中有20个随机整数,取值范围为 0 - 10,

1. 则可以根据这个有限的范围建立一个长度为 11 的统计数组,数组下标从 0 - 10,元素初始值全为 0

2. 遍历这个无序随机数组,每一个整数按照其值对应的统计数组下标元素加 1

3. 遍历统计数组,其下标代表无序随机数组中的元素,其value代表该元素出现的次数

代码如下:

    function countSort(arr: Array<number>):Array<number> {
        // 1. 拿到数列的最大值
        let max = arr[0];
        for (let index = 1; index < arr.length; index++) {
            if(arr[index] > max) {
                max = arr[index]
            }        
        }
    
    
        // 2. 根据最大值确定统计数组长度
        let countArray = (new Array(max + 1)).fill(0);
    
    
        // 3. 遍历无序数组 填充统计数组
        for (let index = 0; index < arr.length; index++) {
            countArray[arr[index]]++    
        }
    
    
        // 遍历统计数组输出结果
        let sortedArray = new Array();
        for (let index = 0; index <= countArray.length; index++) {
            for (let j = 0; j < countArray[index]; j++) {
                sortedArray.push(index)   
            }
        }
        return sortedArray
    }
    
    
    function main() {
        let arr = [4, 4, 6, 5, 3, 2, 8, 1, 7, 5, 6, 0, 10];
        console.log(countSort(arr))
    }
    main()
 

优化1

问题:只以最大值决定数列长度并不严谨,例如以下数列:

95, 94, 91, 98, 99, 90, 99, 93, 91, 92

这时 最大值是 99,最小值是 90,如果创建长度为 100 的数组,那么从 0 到 89 的空间位置都浪费了

解决:以数列 最大值 - 最小值 + 1 作为长度即可,同时,数列最小值作为一个偏移量,用作计算整数在统计数组中的下标

代码如下:

    function countSort(arr: Array<number>) {
        // 1. 拿到最大值和最小值
        let max = arr[0];
        let min = arr[0];
        for (let index = 1; index < arr.length; index++) {
            if(arr[index] > max) {
                max = arr[index]
            }        
            if(arr[index] < min) {
                min = arr[index]
            }
        }
    
    
        // 2. 根据最大值和最小值确定数组长度
        let length = max - min + 1;
        let countArray = (new Array(length)).fill(0)
        
        // 3. 统计对应元素个数
        for (let index = 0; index < arr.length; index++) {
            countArray[arr[index] - min]++        
        }
    
    
        // 4. 遍历统计数组 输出结果
        let sortedArray = []
        for (let index = 0; index < countArray.length; index++) {
            for (let j = 0; j < countArray[index]; j++) {
                sortedArray.push(index + min)            
            }        
        }
    
    
        return sortedArray
    }
    
    
    
    function main() {
        let arr = [95, 94, 91, 98, 99, 90, 99, 90, 99, 93, 91, 92];
        console.log(countSort(arr))
    }
    main()
 

优化2

如果只是单纯地给整数排序,这样的做法并没有问题,但是如果在现实业务中,例如给学生的考试分数进行排序,遇到相同的分数就会分不清谁是谁

如下例子:

排序-4-计数排序

给出学生成绩表,要求按照成绩从低到高排序,如果成绩相同,则遵循原表固有顺序,那么当我们填充统计数组之后,只知道有两个并列成绩为 95 的同学,却不知道哪一个是 小红,哪一个是小绿

排序-4-计数排序

解决方法:

1. 首先将统计数组变形为如下:

排序-4-计数排序

变形的方法为 从数组第二个元素开始,每一个元素都加上前边所有元素之和

这样做的目的是让统计数组中储存的元素值,等于相应整数最终排序位置的序号

2. 创建 sortedArray 数组,长度和输入数列一致,然后从后往前遍历输入数列,

遍历成绩表最后一名 小绿 的成绩,成绩为 95,找到下标为 5 的元素,值为 4,代表小绿的成绩排在第 4 位,同时给统计数组下标识 5 的元素值减 1,从 4 变成 3,代表下次再遇到 95 分成绩时,排在第 3 位,

排序-4-计数排序

遍历成绩表倒数第二名,小白的成绩 94,找到统计数组下标为 4 的元素,值为 2,代表小白的成绩排在第 2 位,同时统计数组下标为 4 的元素减 1,从 2 变为 1,代表下次再遇到 94 分成绩的排在第 1 位(实际已经遇不到了)

排序-4-计数排序

遍历成绩表倒数 第三名,小红同学的成绩,操作同上,排在第 3 位,统计数组下标为 5 的元素值减 1

排序-4-计数排序

这样一来,同样分数的同学就能按照原有的顺序排序了,也正是因此,优化版本的计数排序属于稳定排序

代码如下:

    function countSort(arr: Array<number>) {
        // 1. 拿到最大值和最小值
        let max = arr[0];
        let min = arr[0];
        for (let index = 1; index < arr.length; index++) {
            if(arr[index] > max) {
                max = arr[index]
            }        
            if(arr[index] < min) {
                min = arr[index]
            }
        }
    
    
        // 2. 根据最大值和最小值确定数组长度
        let length = max - min + 1;
        let countArray = (new Array(length)).fill(0)
        
        // 3. 统计对应元素个数
        for (let index = 0; index < arr.length; index++) {
            countArray[arr[index] - min]++        
        }
    
    
        // 4. 统计数组做变形 后边元素值为前边元素值之和
        for (let index = 1; index < countArray.length; index++) {
            countArray[index] += countArray[index - 1]
        }
    
    
        // 5. 倒序遍历原数组,从统计数组中找到位置,填入结果数组
        let sortedArray = new Array(arr.length);
        for (let index = arr.length - 1; index >= 0; index--) {
            // -1 是因为 元素填入数组是 数组下标从 0 开始
            sortedArray[countArray[arr[index] - min] - 1] = arr[index]
            countArray[arr[index] - min]--
        }
        return sortedArray
    }
    
    
    function main() {
        let arr = [95, 94, 91, 98, 99, 90, 99, 90, 99, 93, 91, 92];
        console.log(countSort(arr))
    }
    main()
    
    	
 

小结

复杂度:

如果原始数列的规模为 n,最大和最小整数的差值为 m,

则总体运算量为 3n + m,时间复杂度为O(n + m)

空间复杂度:如果不考虑输出数组,只考虑统计数组的话,则空间复杂度为O(m)

局限性:

1. 当数列最小值和最大值差距过大时,并不适合用计数排序

2. 当数列元素不是整数时,也不适合用计数排序

摘要总结自: 漫画算法 小灰的算法之旅

回复

我来回复
  • 暂无回复内容