排序算法8-计数排序

计数排序

• 平均时间复杂度:O(n+k)
• 最好情况:O(n+k)
• 最坏情况:O(n+k)
• 空间复杂度:O(k)
• 排序方式:Out-place
• 稳定性:稳定

算法步骤:
1.找出待排序的数组中最大值
2.统计数组中每个值为i的元素出现的次数，存入数组的第i项
3.对所有的计数累加
4.填充目标数组

function countSort(arr) {
  //最大值的获取直接通过api获取
  let maxValue = Math.max(...arr);
  let len2 = maxValue + 1;
  let arr2 = new Array(len2);
  let index = 0;
  let len = arr.length;

  for (let i = 0; i < len; i++) arr2[arr[i]] = (arr2[arr[i]] || 0) + 1;
  for (let j = 0; j < len2; j++) {
    while (arr2[j] > 0) {
      arr[index++] = j;
      arr2[j]--;
    }
  }
}