在JavaScript中实现计数排序

我们需要编写一个JavaScript函数，该函数接受一个数字数组并使用计数排序算法对其进行排序。

如果知道最大值，则可以使用计数排序算法对线性时间和空间中的数字数组进行排序。使用最大值创建一个具有该大小的数组，以计算每个索引值的出现。

然后，我们将计数为非零的所有索引提取到结果数组中。

首先，我们将使用一个循环来找出数组的最大元素，一旦有了，我们将使用计数排序对数组进行排序。

示例

const arr = [4, 3, 1, 2, 3];
const findMaximum = arr => arr.reduce((acc, val) => val > acc ? val: acc, Number.MIN_VALUE)
const countingSort = (arr = []) => {
   const max = findMaximum(arr);
   const counts = new Array(max + 1);
   counts.fill(0);
   arr.forEach(value => counts[value]++);
   const res = [];
   let resultIndex = 0;
   counts.forEach((count, index) => {
      for (let i = 0; i < count; i++) {
         res[resultIndex] = index;
         resultIndex++;
      };
   });
   return res;
};
console.log(countingSort(arr));

输出结果

控制台中的输出将是-

[ 1, 2, 3, 3, 4 ]