计数排序

什么是计数排序

“计数排序”，名副其实，就是根据”计数”的方式来进行排序，所谓”计数”，就是统计每个元素重复出现的次数。

正如上述原始数列有5个数值，数值范围从1-5。

// 原始数列
let arr = [5,4,3,2,3,1]

那么，这些整数的值肯定是在1，2，3，4，5这5个数里面。

所以可以根据这个整数的取值范围，建立一个长度为6的数组(包括0，所以长度为6)，数组下标从0到5，元素初始值全部为0。

// 用于计数的数组,数组长度为6，初始值全为0
let countingArr = [0,0,0,0,0,0]

接着根据原始数列中元素出现的次数和顺序，加入到计数数组中。

// 用于计数的数组,数组长度为6，初始值全为0
let countingArr = [0,0,0,0,0,0]
// 原始数组第一个元素为5，则在计数数组下标为5的位置加1
countingArr[5] += 1
// 以此类推，原始数组第二个元素为4，则在计数数组下标为4的位置加1
countingArr[4] += 1
// 以此类推，原始数组第三个元素为3，则在计数数组下标为3的位置加1
countingArr[3] += 1
// 以此类推，原始数组第四个元素为2，则在计数数组下标为2的位置加1
countingArr[2] += 1
// 以此类推，原始数组第五个元素为3，则在计数数组下标为3的位置加1
countingArr[3] += 1
// 以此类推，原始数组第六个元素为1，则在计数数组下标为1的位置加1
countingArr[1] += 1
// 最终得到的计数数组如下
console.log(countingArr)
// [0,1,1,2,1,1]

我们得到计数数组这个”统计结果”，排序就简单了。

后续的操作便是遍历数组，输出数组元素的下标值，元素的值是几，就输出几次。

// 计数排序后的结果
let result = [1,2,3,3,4,5]

总结

计数排序是使用空间换时间的排序算法，虽然使用它排序的速度很快，但是当数列的最大值最小值之间的插值鸿沟过大时，不适合计数排序(假设20个随机数，数值范围从0到10亿，就需要开辟10亿个数组空间，不仅浪费空间，而且时间复杂度也高)；其次，计数排序只适合用于整数的数列元素场景，因为计数排序本身无法统计小数。

代码实现

/**
 * 找到数组中最大的一项
 * @param {array} array 需要操作最大值的数组
 * @param {function} compareFn // 比较用的方法，默认为defaultCompare
 * @returns {number}} 返回数组中找到的最大值
 */
export function findMaxValue(array, compareFn = defaultCompare) {
  // 要找到数组中的最大值，我们只需要迭代并找到值最大的一项即可
  if (array && array.length > 0) { 
    let max = array[0]; 
    for (let i = 1; i < array.length; i++) {
      if (compareFn(max, array[i]) === Compare.LESS_THAN) {
        max = array[i];
      }
    }
    return max;
  }
  return undefined;
}
/**
 * 计数排序
 * @param {array} array 要进行排序的数组
 * @returns {array} 返回排序后的数组
 */
export function countingSort(array) {
  if (array.length < 2) { // 如果待排序的数组为空或只有一个元素，则不需要运行排序算法。
    return array;
  }
  const maxValue = findMaxValue(array); // 找到数组中的最大值
  let sortedIndex = 0;
  const counts = new Array(maxValue + 1); // 创建计数数组，从索引 0 开始直到最大值索引 value + 1
  array.forEach(element => {
    // 迭代数组中的每个位置并在 counts 数组中增加元素计数值
    if (!counts[element]) { // 为了保证递增成功，如果 counts 数组中用来计数某个元素的位置一开始没有用 0 初始化的话
      counts[element] = 0; // 我们将其赋值为 0
    }
    counts[element]++;
  });
  // console.log('Frequencies: ' + counts.join());
   // 所有元素都计数后，我们要迭代 counts 数组并构建排序后的结果数组
  counts.forEach((element, i) => {
    while (element > 0) {
      array[sortedIndex++] = i; // 由于可能有多个元素有相同的值，我们要将元素按照在原始数组中的出现次数进行相加
      element--; // 减少计数值,直到它为0
    }
  });
  return array;
}