跳到主要内容

基数排序

2024年04月03日
柏拉文
越努力，越幸运

一、认识​

基数排序英文称Radix sort，是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串和特定格式的浮点数，所以基数排序也仅限于整数。它首先将所有待比较数值，统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。

特点：

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

扩展:

  • 排序算法的稳定性:

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

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

二、思想​

2.1 以基数为参考点，记录基数个数(计数思想)​

  1. 寻找 array 中的最大值，确定最大位数
  2. 通过最大位数，确定最大位数长度，作为后面基数获取的边界条件
  3. array 中的元素以个位数为基数，通过计数进行排序
  4. array 中的元素以十位数为基数，通过计数进行排序
  5. 依次类推即可

注意：

  • 对包含负数的数组进行排序时:
    • 获取基数: redix=parseInt(nums[i]/digit)%10+9
    • 计数数组: 申请长度为 19 的计数数组，用来存储 [-9,9] 的所有整数

2.2 以基数为参考点，存取对应元素​

  1. 寻找 array 中的最大值，确定最大位数
  2. 通过最大位数，确定最大位数长度，作为后面基数获取的边界条件
  3. array 中的元素以个位数为基数，以基数为参考点，创建 行长度为为 10 ，列为数组的二维数组 bucketArray，元素初始值为 0。行长度用来表示 基数的 0-9。用来存放通过基数区分的元素。依次将元素放入相对应的 bucketArray[基数] 中,随后从左往右遍历 bucketArray 放入 array
  4. array 中的元素以十位数为基数，以基数为参考点，创建 行长度为为 10 ，列为数组的二维数组 bucketArray，元素初始值为 0。行长度用来表示 基数的 0-9。用来存放通过基数区分的元素。依次将元素放入相对应的 bucketArray[基数] 中,随后从左往右遍历 bucketArray 放入 array 中
  5. 依次类推即可

注意：

  • 对包含负数的数组进行排序时:
    • 获取基数: redix=parseInt(nums[i]/digit)%10+9
    • 桶数组: 申请长度为 19 的桶数组，用来存储 [-9,9] 的所有整数

三、实现​

3.1 以基数为参考点，记录基数个数(计数思想)​

function countSort(nums,digit){
    let range=19;
    let countNums=new Array(range).fill(0);
    for(let item of nums){
        let redix=parseInt(item/digit)%10+9;
        countNums[redix]++;
    }
    for(let i=1;i<range;i++){
        countNums[i]+=countNums[i-1];
    }
    let result=[];
    for(let i=nums.length-1;i>=0;i--){
        let redix=parseInt(nums[i]/digit)%10+9;
        result[--countNums[redix]]=nums[i];
    }
    for(let i=0;i<result.length;i++){
        nums[i]=result[i];
    }
}
function sortArray(nums){
    let max=Math.abs(nums[0]);
    for(let item of nums){
        if(max<Math.abs(item)){
            max=Math.abs(item);
        }  
    }
    let maxDigit=String(max).length;
    for(let i=0,digit=1;i<maxDigit;i++,digit*=10){
        countSort(nums,digit);
    }
    return nums;
}

3.2 以基数为参考点，存取对应元素(桶思想)​

function sortArray(nums){
    let max=Math.abs(nums[0]);
    for(let item of nums){
        if(max<Math.abs(item)){
            max=Math.abs(item);
        }  
    }
    let maxDigit=String(max).length;
    let range=19;
    for(let i=0,digit=1;i<maxDigit;i++,digit*=10){
        let bucketNums=new Array(range).fill(0).map(value=>new Array());
        for(let j=0;j<nums.length;j++){
            let redix=parseInt(nums[j]/digit)%10+9;
            bucketNums[redix].push(nums[j]);
        }
        let index=0;
        for(let j=0;j<range;j++){
            if(bucketNums[j].length){
                for(let k=0;k<bucketNums[j].length;k++){
                    nums[index++]=bucketNums[j][k];
                }
            }
        }
    }
    return nums;
}