JS实现的计数排序与基数排序算法示例

深入了JavaScript中的计数排序和基数排序算法。这两种排序方法各具特色，适用于不同的场景。

计数排序

计数排序是一种简单的桶排序形式。在这种方法中，我们使用一个额外的数组（也称为桶数组），其大小等于待排序数组的可能值的范围。每个桶代表一个数字在数组中出现的次数。这种方法的时间复杂度为O(n)，其中n是数组的大小，而空间复杂度则取决于数组数字的范围。由于其特殊性质，计数排序通常用于范围较小的整数排序。以下是JavaScript中的计数排序实现：

```javascript

function countSort(arr) {

var len = arr.length;

var maxVal = Math.max(...arr); // 获取最大值以确定桶的数量

var bucketArr = new Array(maxVal + 1).fill(0); // 创建桶数组并初始化所有值为0

var resArr = new Array(len); // 创建结果数组以存储排序后的值

// 统计每个值出现的次数

for (let i = 0; i < len; i++) {

bucketArr[arr[i]]++;

}

// 计算每个值的累积计数，使其成为索引值

for (let i = 1; i < bucketArr.length; i++) {

bucketArr[i] += bucketArr[i - 1];

}

// 使用累积计数将值放入结果数组

for (let i = len - 1; i >= 0; i--) {

resArr[--bucketArr[arr[i]]] = arr[i]; // 使用递减操作确保正确索引值

}

return resArr; // 返回排序后的数组

}

```

基数排序

基数排序是一种多趟的桶排序算法。它是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。基数排序是基于待排序数组中的元素值的每一位进行排序的一种算法。以下是基数排序的JavaScript实现：