计数排序 js代码，并通俗易懂的解释

下面是JS实现的计数排序代码及解释：

function countingSort(arr) {
  // 找出最大值和最小值
  let max = arr[0], min = arr[0];
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] > max) {
      max = arr[i];
    }
    if (arr[i] < min) {
      min = arr[i];
    }
  }
  // 统计每个元素出现的次数
  const counts = new Array(max - min + 1).fill(0);
  for (let i = 0; i < arr.length; i++) {
    counts[arr[i] - min]++;
  }
  // 计算前缀和
  for (let i = 1; i < counts.length; i++) {
    counts[i] += counts[i - 1];
  }
  // 根据前缀和将元素放到有序序列中的正确位置
  const result = new Array(arr.length);
  for (let i = arr.length - 1; i >= 0; i--) {
    result[counts[arr[i] - min] - 1] = arr[i];
    counts[arr[i] - min]--;
  }
  return result;
}

该算法的主要思想是先找出待排序序列中的最大值和最小值，然后根据最大值和最小值确定统计数组的大小。接着遍历待排序序列，统计每个元素出现的次数，存入统计数组中；然后对于统计数组中的每个元素，计算其前缀和，得到每个元素在有序序列中的起始位置；最后从后往前遍历待排序序列，根据统计数组和前缀和将元素放到有序序列中的正确位置。

具体来说，我们首先遍历一遍待排序序列，找出其中的最大值和最小值，然后根据最大值和最小值确定统计数组的大小。然后我们再遍历一遍待排序序列，统计每个元素出现的次数，存入统计数组中。接着我们计算统计数组的前缀和，得到每个元素在有序序列中的起始位置。最后，从后往前遍历待排序序列，根据统计数组和前缀和将元素放到有序序列中的正确位置。

需要注意的是，在统计数组中存放的是元素出现的次数，而不是元素本身。另外，为了避免负数索引，我们需要将所有元素减去最小值，再进行统计排序。