计数排序与基数排序：非比较排序算法

在计算机科学中，排序算法是处理数据的基本工具。传统的比较排序算法，如快速排序、归并排序等，依赖于元素间的比较来进行排序。然而，在某些情况下，这些算法可能不是最优选择。非比较排序算法提供了一种替代方案，它们不依赖于元素之间的比较，而是通过其他方法对数据进行排序。本文将重点介绍两种非比较排序算法：计数排序和基数排序。

计数排序

算法原理

计数排序是一种线性时间复杂度的排序算法，适用于整数排序。它的工作原理如下：

1. 确定最大值：首先找到待排序数组中的最大值。
2. 创建计数数组：创建一个大小为最大值加一的数组，用于存储每个值出现的次数。
3. 填充计数数组：遍历原数组，统计每个值出现的次数，并记录在计数数组对应的位置。
4. 生成排序结果：从计数数组的末尾开始，构建排序后的数组。每次取出一个值，根据计数数组中该值的数量，将其添加到排序数组中相应的位置。

示例代码（JavaScript）

function countingSort(arr) {
    const maxVal = Math.max(...arr);
    const count = new Array(maxVal + 1).fill(0);

    // 统计每个元素出现的次数
    arr.forEach(num => {
        count[num]++;
    });

    let sortedArr = [];
    // 构建排序后的数组
    for (let i = count.length - 1; i >= 0; i--) {
        while (count[i] > 0) {
            sortedArr.push(i);
            count[i]--;
        }
    }

    return sortedArr;
}

// 示例使用
const arr = [4, 2, 2, 8, 3, 3, 1];
console.log(countingSort(arr)); // 输出: [1, 2, 2, 3, 3, 4, 8]

基数排序

算法原理

基数排序是一种基于计数排序的扩展，适用于处理整数排序。它的主要思想是将整数按照位数进行分组，分别对每一位进行计数排序。基数排序分为多个步骤，每个步骤处理整数的一个位数。例如，对于十进制数，可以先按个位排序，然后按十位排序，以此类推。

示例代码（JavaScript）

基数排序实现时，需要考虑不同位数的处理方式。以下是一个简单的基数排序实现：

function radixSort(arr) {
    const maxVal = Math.max(...arr);
    const exp = 1;

    while (Math.floor(maxVal / exp) > 0) {
        arr = countingSort(arr);
        exp *= 10;
    }

    return arr;
}

// 示例使用
const arr = [170, 45, 75, 90, 802, 24, 2, 66];
console.log(radixSort(arr)); // 输出: [2, 24, 45, 66, 75, 90, 170, 802]

总结

计数排序和基数排序都是非比较排序算法，适用于特定类型的数据和场景。计数排序简单高效，适用于整数范围较小的情况；基数排序则更适用于整数位数较多或需要稳定排序的情况。在实际应用中，选择哪种排序算法取决于数据的特性和具体需求。