计数排序

[myLightLin]

简介

排序算法	时间复杂度	是否基于比较
冒泡、插入、选择	O（n²）	√
快排、归并、希尔、堆	O（nlogn）	√
桶、计数、基数	O（n）	×

计数排序，是桶排序的一种特殊情况。假设数据的值所处的范围并不大，就可以把数据分成 k 个桶，每个桶存放的都是相同的数据，这样省去了对桶排序的时间，直接依次从桶里取出数据就是有序的。

代码

function countingSort(arr) {
  if (arr.length <= 1) return
  const max = findMaxValue(arr)
  const counts = new Array(max + 1)
  const n = arr.length
  // 下标为元素，值是元素个数
  for (let i = 0; i < n; i++) {
    if (!counts[arr[i]]) {
      counts[arr[i]] = 0
    }
    counts[arr[i]]++
  }
  let sortedIndex = 0
  for (let i = 0; i < counts.length; i++) {
    while (counts[i] > 0) {
      arr[sortedIndex] = i
      sortedIndex++
      counts[i]--
    }
  }
}

function findMaxValue(arr) {
  let max = arr[0]
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] > max) {
      max = arr[i]
    }
  }
  return max
}

总结

1. 时间复杂度 O（n）,空间复杂度 O（1）
2. 适合处理非负整数的情况
3. 适合数据范围不大的情况