[游戏开发]算法：计数排序

前言

如果想深入了解的话建议先看看 算法概述

为了方便用来测试的数组一成不变，我们可以来一个随机数组

const arr = []
const arrLength = 11 //可以随机长度 Math.floor(Math.random() * 30) + 1
for (let i = 0; i < arrLength; i++) {
    arr.push(Math.floor(Math.random() * 99) + 1)
}
console.log(arr, 'arr')

算法描述

计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

这个算法比较简单，直接看图上代码

动图演示

代码实现

function countingSort(arr) {
  const bucket = [];

  for (var i = 0; i < arr.length; i++) {
    if (!bucket[arr[i]]) {
      bucket[arr[i]] = 0;
    }
    bucket[arr[i]]++;
  }

  let sortedIndex = 0

  //方式1：利用forEach会跳过稀疏数组中的空位（js中的Array在内存中是不连续的）快速循环
  bucket.forEach(function (value,key) {
    while (value--) {//先作为值参与比较后，才会减一
      arr[sortedIndex++] = parseInt(key);
    }
  })
  
  //方式2：利用Object.keys()获取有值的key,但是key是String类型
  // let keys = Object.keys(bucket);
  // for (var j = 0; j < keys.length; j++) {
  //   while (bucket[keys[j]]--) {//先作为值参与比较后，才会减一
  //     arr[sortedIndex++] = parseInt(keys[j]);
  //   }
  // }

  return arr;
}

算法分析

计数排序是一个稳定的排序算法。当输入的元素是 n 个 0到 k 之间的整数时，时间复杂度是O(n+k)，空间复杂度也是O(n+k)，其排序速度快于任何比较排序算法。当k不是很大并且序列数据量不是特别大且比较集中时，计数排序是一个很有效的排序算法。

PS：桶排序 是计数排序的升级版

复杂度

最坏时间复杂度：O(n+k)
最好时间复杂度：O(n+k)
平均时间复杂度：O(n+k)
空间复杂度：O(n+k)
稳定性：稳定

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖