数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究在 JavaScript 中实现计数排序
在给定的任务中，我们的目标是创建一个计数排序技术，并借助 Javascript 功能来实现此问题。
什么是计数排序？
计数排序是一种根据键对对象数据集进行排序的过程。它通过计算具有不同键值的项目的数量并查找每个对象在排序输出中的位置来工作。计数排序的思想是将项目直接放置到输出数组中的正确位置。
在算法开始时，我们需要找到输入数组中的最大值和最小值。借助这些值，我们需要创建一个与输入数组中值长度相等的计数数组。计数数组将存储数组中每个不同值的出现次数。
该算法使用计数数组的前缀和。因此，该算法以相反的顺序遍历输入数组，并根据其计数将每个项目放置到输出数组中的正确位置，并相应地递减计数。
给定问题的逻辑
在给定的问题陈述中，我们必须使用上面提到的计数排序来完成对给定数组的项目进行排序的任务。因此，我们首先将获取一个输入数组，并将其作为新数组返回，该数组已排序且与输入数组的长度相同。
根据计数排序技术，我们需要找出输入数组中的最大值和最小值。然后，我们将迭代数组元素并计算每个项目的出现次数。然后计算计数数组的前缀和。然后再次遍历数组并将每个项目放在其正确的位置。
算法
步骤 1 - 检查给定数组是否有元素。
步骤 2 - 声明计数和输出数组。计数数组将用于计算每个值出现的次数。排序数组将用于保存输出数组。
步骤 3 - 使用 for 循环遍历给定数组，并计算其中每个值的重复次数。
步骤 4 - 根据计数排序算法计算数组的前缀和。
步骤 5 - 以相反的顺序遍历给定数组，将每个项目放在正确的位置。
步骤 6 - 最后，我们必须将输出显示为排序数组。
算法代码
function countingSort(arr) {
if (arr.length === 0) {
return arr;
}
// Define the range of values in the input array
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];
}
}
// initialize the required arrays
const count = new Array(max - min + 1).fill(0);
const output = new Array(arr.length);
// count the number of occurrences
for (let i = 0; i < arr.length; i++) {
count[arr[i] - min]++;
}
// calculate the prefix sum of the count array
for (let i = 1; i < count.length; i++) {
count[i] += count[i - 1];
}
// the output array in sorted order
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 操作来完成任务。该算法根据给定的问题陈述使用计数排序。
1K+ 浏览量
