解题思路 or 实现原理

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

算法步骤

实现代码

/*
 * @Author: Rainy
 * @Date: 2019-11-14 19:25:01
 * @LastEditors: Rainy
 * @LastEditTime: 2019-11-24 17:52:06
 */

import { NumberArrayMap } from 'types';

export function countingSort(arr: NumberArrayMap, maxValue: number): NumberArrayMap {
  let bucket: NumberArrayMap = new Array(maxValue + 1);
  let sortedIndex = 0;
  let arrLen = arr.length;
  let bucketLen = maxValue + 1;
  if (arr.length < 2) {
    return arr;
  }

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

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

  return arr;
}

参考

countingSort (opens new window)