/**
 * @description 计数排序, 只能对大于零的整数排序
 * @param {number[]} arr - 需要排序的数组
 */
export function countSort(arr) {
  const len = arr.length;
  const counts = []; // 用于计数的数组
  // 遍历整个数组
  for (let i = 0; i < len; i++) {
    const el = arr[i];
    counts[el] = counts[el] ? counts[el] + 1 : 1;
  }
  let index = 0;
  for (let i = 0; i < counts.length; i++) {
    let time = counts[i];
    while (time) {
      // 当桶子不为空时，遍历time次
      arr[index++] = i;
      time--;
    }
  }
  return arr; // 返回与不反都可以，本身就是对原数组的操作
}

/**
 * @description 修改后的计数排序，支持负数
 * @param {number[]} arr - 要排序的整数数组
 */
export function countSort2(arr) {
  // 先找出最大值和for
  const n = arr.length;
  let min = arr[0];
  let max = arr[0];
  for (let i = 0; i < n; i++) {
    if (arr[i] > max) {
      max = arr[i];
    }
    if (arr[i] < min) {
      min = arr[i];
    }
  }
  // 计算计数数组的大小
  const size = max - min + 1;
  const counts = new Array(size).fill(0);
  // 遍历原数组把"值-min"作为计数数组的下标, 值-min能保证下标永 远不会小于零
  for (let i = 0; i < n; i++) {
    counts[arr[i] - min]++;
  }
  // 遍历counts数组， 累计前面的下下标值
  for (let i = 1; i < size; i++) {
    counts[i] += counts[i - 1];
  }
  const ret = [];// 排序后的新数组
  // 现在数组的下表就是值，值就是下标
  for (let i = n - 1; i >= 0; i--) {
    counts[arr[i] - min]--; // 假设我们有三个数放入counts中，counts[0]=1,counts[1]=2,counts[2]=3,所以要先减1再做下标使用
    ret[counts[arr[i] - min]] = arr[i];
  }
  return ret;
}