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)，因为我们创建了两个数组：一个是计数数组，另一个是输出数组。