Java教程

JavaScript算法---排序(计数排序)【6】

本文主要是介绍JavaScript算法---排序(计数排序)【6】,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
  • 该算法于1954年由 Harold H. Seward提出,通过计数将时间复杂度降到了O(N+k)。
  • 计数排序分布式排序

原理:需要创建一个临时数组,存放出现的次数。等所有元素都计数完成后,迭代临时数组构建排序后的结果。

在这里插入图片描述

function countingSort(array) {
  if (array.length < 2) {
    // 如果待排序数组为空或只有一个元素,则不需运行排序
    return array;
  }
  
  const maxValue = Math.max(...array); // {2} 从索引0开始,找到数组中的最大值
  const counts = new Array(maxValue + 1); // {3} 创建计数数组,比如最大值为3,则创建4个,最后一个下标为3
  array.forEach((element) => {
    if (!counts[element]) {
      // {4} 如果计数某个元素一开始没有初始化,则赋值为0
      counts[element] = 0;
    }
    // 给计数数组对应的下标加
    counts[element]++; // {5}
  });
  // 辅助索引,帮助我们将值赋值到结果数组中的正确位置
  let sortedIndex = 0;
  counts.forEach((count, i) => {
    while (count > 0) {
      // {6}
      array[sortedIndex++] = i; // {7}
      count--; // {8}
    }
  });
  return array;
}
console.log(countingSort([3,5,1,9,2]));

满足下列2点可以最大程度发挥计数排序的优势

  1. 排序的元素必须是整数
  2. 排序元素的取值要在一定范围内,并且比较集中
这篇关于JavaScript算法---排序(计数排序)【6】的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!