在 JavaScript 中实现计数排序
在给定的任务中，我们的目标是创建一种计数排序技术，并借助 Javascript 功能实现此问题。
什么是计数排序?
计数排序是按键对对象数据集进行排序的过程。它的工作原理是计算具有不同键值的项目数量，并找到每个对象在排序输出中的位置。计数排序的思想是将项目直接放入输出数组中的正确位置。
在算法开始时，我们需要找到输入数组中的最大值和最小值。借助这些值，我们需要创建一个计数数组，其值的长度与输入数组中的值相等。计数数组将存储数组中每个不同值的出现次数。
该算法使用计数数组的前缀和。因此，该算法以相反的顺序遍历输入数组，并根据计数将输出数组中的每个项目放置在正确的位置，并相应地减少计数。
给定问题的逻辑
在给定的问题陈述中，我们必须借助上述计数排序对给定数组的项目进行排序。因此，首先我们将获取一个输入数组，并将输出作为新数组返回，该新数组的长度与输入数组的长度相同。
根据计数排序技术，我们需要找出输入数组中的最大值和最小值。然后，我们将迭代数组元素并计算每个项目的出现次数。然后计算计数数组的前缀和。然后再次遍历数组并将每个项目放置在正确的位置。
算法
步骤 1 - 检查给定数组是否包含元素。
步骤 2 - 声明计数和输出的数组。计数数组将用于计算每个值出现的次数。排序后的数组将用于保存输出数组。
步骤 3 - 使用 for 循环遍历给定的数组，并计算其中每个值的重复次数。
步骤 4 - 根据计数排序算法计算数组的前缀和。
步骤 5 - 以相反的顺序遍历给定的数组，将每个项目放在正确的位置。
步骤 6 - 最后，我们必须将输出显示为排序后的数组。
算法代码
function countingSort(arr) {
if (arr.length === 0) {
return arr;
}
// 定义输入数组中的值的范围
let min = arr[0];
let max = arr[0];
for (let i = 1; i < arr.length; i++) {
if (arr[i] < min) {
min = arr[i];
}
if (arr[i] > max) {
max = arr[i];
}
}
// 初始化所需数组
const count = new Array(max - min + 1).fill(0);
const output = new Array(arr.length);
// 计算出现的次数
for (let i = 0; i < arr.length; i++) {
count[arr[i] - min]++;
}
// 计算 count 数组的前缀和
for (let i = 1; i < count.length; i++) {
count[i] += count[i - 1];
}
// 按排序顺序输出数组
for (let i = arr.length - 1; i >= 0; i--) {
output[count[arr[i] - min] - 1] = arr[i];
count[arr[i] - min]--;
}
return output;
}
const arr = [30, 10, 40, 10, 50, 90, 20, 60, 50, 30, 50];
console.log(countingSort(arr));
复杂性
计数排序函数的时间复杂度为 O(n+m)，其中 n 是输入数组的长度，m 是输入数组中值的范围。如代码所示，我们迭代了一次数组来计算每个值的重复次数。然后我们迭代了计数数组一次来计算前缀和。因此，执行代码所需的总体时间为 O(n+m)。空间复杂度也是 O(n+m)。因为我们创建了两个数组，一个是计数，另一个是输出数组。
结论
我们看到的对数组中的元素进行排序的代码利用基本的 JavaScript 操作来完成任务。该算法根据给定的问题陈述使用计数排序。
