第 89 期(算法-排序)：经典排序算法之计数排序

[wingmeng]

计数排序

计数排序是一个非基于比较的排序算法，元素从未排序状态变为已排序状态的过程，是由额外空间的辅助和元素本身的值决定的。

• 原理： 将待排序集合中的每个元素值本身大小作为下标，依次进行存放，记录每个元素的存放次数，根据额外空间已经确定的元素序列，移动待排序集合元素到已排序集合中。
• 复杂度： 时间复杂度：Ο(n+k)（其中k是整数的范围）

算法分析：

由算法示例可知，计数排序的时间复杂度为 。因为算法过程中需要申请一个额外空间和一个与待排序集合大小相同的已排序空间，所以空间复杂度为 。由此可知，计数排序只适用于元素值较为集中的情况，若集合中存在最大最小元素值相差甚远的情况，则计数排序开销较大、性能较差。通过额外空间的作用方式可知，额外空间存储元素信息是通过计算元素与最小元素值的差值作为下标来完成的，若待排序集合中存在元素值为浮点数形式或其他形式，则需要对元素值或元素差值做变换，以保证所有差值都为一个非负整数形式。

来源：https://www.jianshu.com/p/86c2375246d7

function countingSort(arr, maxValue) {
  var bucket = new Array(maxValue+1),
      sortedIndex = 0;
      arrLen = arr.length,
      bucketLen = maxValue + 1;

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

  for (var j = 0; j < bucketLen; j++) {
    while(bucket[j] > 0) {
      arr[sortedIndex++] = j;
      bucket[j]--;
    }
  }

  return arr;
}