0324.md

计数排序

以数组元素值为键，出现次数为值存进一个临时数组，最后再遍历这个临时数组还原回原数组。因为 JavaScript 的数组下标是以字符串形式存储的，所以计数排序可以用来排列负数，但不可以排列小数。

• 最好： O(n + k)，k是最大值和最小值的差。
• 最坏： O(n + k)
• 平均： O(n + k)

function countingSort(nums) {
  if (!Array.isArray(nums)) {
    return new TypeError('not a array');
  }
  if (nums.length < 2) {
    return nums;
  }
  let array = [];
  let max = Math.max(...nums);
  let min = Math.min(...nums);
  // 装桶
  let len = nums.length;
  for (let i = 0; i < len; i++) {
    let temp = nums[i];
    array[temp] = array[temp] + 1 || 1;
  }
  let index = 0;
  // 还原原数组
  for (let i = 0; i <= max; i++) {
    while (array[i] > 0) {
      nums[index++] = i;
      array[i]--;
    }
  }
}

计数排序优化

把每一个数组元素都加上 min 的相反数，来避免特殊情况下的空间浪费，通过这种优化可以把所开的空间大小从 max+1 降低为 max-min+1， max 和 min 分别为数组中的最大值和最小值。

比如数组 [103, 102, 101, 100]，普通的计数排序需要开一个长度为 104 的数组，而且前面 100 个值都是 undefined，使用该优化方法后可以只开一个长度为 4 的数组。

function countingSort2(nums) {
  if (!Array.isArray(nums)) {
    return new TypeError('not a array');
  }
  if (nums.length < 2) {
    return nums;
  }
  let array = [];
  let max = Math.max(...nums);
  let min = Math.min(...nums);
  // 加上最小值的相反数来缩小数组范围
  let add = -min;
  let len = nums.length;
  for (let i = 0; i < len; i++) {
    let temp = nums[i];
    temp += add;
    array[temp] = array[temp] + 1 || 1;
  }
  let index = 0;
  for (let i = min; i <= max; i++) {
    let temp = array[i + add];
    while (temp > 0) {
      nums[index++] = i;
      temp--;
    }
  }
}