计数排序

2024年04月03日

柏拉文

越努力，越幸运

一、认识

计数排序英文称Counting sort，是一种稳定的线性时间排序算法。计数排序使用一个额外的数组C，其中第i个元素是待排序数组A中值等于 i的元素的个数。然后根据数组C来将A中的元素排到正确的位置。基本的步骤如下：

找出待排序的数组中最大和最小的元素
统计数组中每个值为i的元素出现的次数，存入数组C的第i项
对所有的计数累加,从C中的第一个元素开始，每一项和前一项相加
反向填充目标数组,将每个元素i放在新数组的第C[i]项，每放一个元素就将C[i]减去1

特点：

稳定排序: 如果 a 原本在 b 的前面，且 a == b，排序之后 a 仍然在 b 的前面,所以计数排序是稳定的
非原地排序: 需要利用额外的数组来辅助排序。
排序方式: Out-place (占用额外内存)
时间复杂度: O(n+k) [n 代表数据规模及数据量大小 k 代表桶的个数]
空间复杂度: O(k) [n 代表数据规模及数据量大小 k 代表桶的个数]

扩展:

排序算法的稳定性:

假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i] = r[j]，且 r[i] 在 r[j] 之前，而在排序后的序列中，r[i] 仍在 r[j] 之前，则称这种排序算法是稳定的；否则称为不稳定的。

那么排序算法的稳定性有什么意义呢？其实它只在一种情况下有意义：当要排序的内容是一个对象的多个属性，且其原本的顺序存在意义时，如果我们需要在二次排序后保持原有排序的意义，就需要使用到稳定性的算法。

二、思想

array 为待排序数组;count 为额外开辟的存储计数的数组

寻找 array 数组中的最大值与最小值 max、min
通过 array 中的最大值创建长度为 max-min+1 的一维数组 countArray（初始值为 0）
countArray 统计 array 数组中每个元素出现的次数，并且存放的索引位置为 array[i] - min 即 countArray[array[i]-min] = array 元素出现的次数
countArray 计数累加。也就是说：countArray 中对每一个元素进行累加操作即每一个元素的值 = 之前元素值的和+当前元素的值
从右往左遍历 array 数组, array 数组中元素在 countArray 中索引位置为 array[i] - min , 通过 array[i] - min ,array 元素找到 countArray 中对应的出现次数出现次数为 countArray[array[i]-min] ,将该元素的出现次数 - 1 ，并填充到新数组 newArray 中去，填充到新数组中的索引位置为该元素出现次数 - 1 ，即为countArray[array[i]-min] - 1
将 newArray 中的元素拷贝至 array

三、实现

function sortArray(nums){
    let max=nums[0];
    let min=nums[0];
    for(let i=0;i<nums.length;i++){
        if(nums[i]>max){
            max=nums[i];
        }
        if(nums[i]<min){
            min=nums[i];
        }
    }
    let range=max-min+1;
    let countNums=new Array(range).fill(0);
    for(let item of nums){
        countNums[item-min]++;
    }
    for(let i=1;i<range;i++){
        countNums[i]+=countNums[i-1];
    }
    let tempNums=[];
    for(let i=nums.length-1;i>=0;i--){
        tempNums[--countNums[nums[i]-min]]=nums[i];
    }
    for(let i=0;i<tempNums.length;i++){
        nums[i]=tempNums[i];
    }
    return nums
}

性能分析:

时间复杂度:O(n+k)
空间复杂度:O(n+k)

一、认识​

二、思想​

三、实现​

一、认识

二、思想

三、实现