带你读《图解算法小抄》十四、排序（21）

function countingSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }
  // 确定数组的范围
  const max = Math.max(...arr);
  const min = Math.min(...arr);
  const range = max - min + 1;
  // 创建计数数组，并初始化为0
  const countArray = new Array(range).fill(0);
  // 统计每个元素出现的次数
  for (let i = 0; i < arr.length; i++) {
    const countIndex = arr[i] - min;
    countArray[countIndex]++;
  }
  // 根据计数数组重新排序原数组
  let sortedIndex = 0;
  for (let i = 0; i < countArray.length; i++) {
    while (countArray[i] > 0) {
      arr[sortedIndex] = i + min;
      sortedIndex++;
      countArray[i]--;
    }
  }
  return arr;
}