JavaScript-计数排序

前言

计数排序是利用hash的数据结构，即key-value，以值为key，出现次数为其value。

相对于比较排序(最优复杂度为nlogn), 计数排序复杂度为O(n+max)

适用

不适用于负数及小数，并消耗较大的空间，特别是数据特别分散时。

JS实现

Array.prototype.countSort = function() {
  const C = []
  for(let i = 0; i < this.length; i++) {
    const j = this[i]
    C[j] >= 1 ? C[j] ++ : (C[j] = 1)
  }
  const D = []
  for(let j = 0; j < C.length; j++) {
    if(C[j]) {
      while(C[j] > 0) {
        D.push(j)
        C[j]--
      }
    }
  }
  return D
}

上述中，若是D通过寻找C中最大值作为循环结束，则要注意循环结束条件是<=.