Counting Sort

Thinking:

• index 是 arr 的 (value - min) !!!!!!!
• index 是 arr 的 (value - min）!!!!!!!

• index 是 arr 的 (value - min) !!!!!!

• the last position that 4(the index of count) can occur is going to be the value at 4, the value is 5

• the last position that 2(the index of count) can occur is going to be the value at 2, the value is 3

    我主要不懂 running  sum，把 running sum 当成新输出数组的长度
    running sum = result.length
  

let arr = [8, 2, 3, 8, 6, 9]
const countingSort = (arr) => {
  let max = Math.max(...arr)
  let min = Math.min(...arr)
  let countLength = max - min + 1
  let counting = new Array(countLength).fill(0)

  //遍历原数组，开始计算每个元素出现的次数， counting the occurrence of each value in the array
  for (let j = 0; j < arr.length; j++)
    counting[arr[j] - min]++;

  //running sum
  for (let v = 1; v < countLength; v++)
    counting[v] += counting[v - 1]

  let result = []
  let runningSum = 0
  for (let k = arr.length - 1; k >= 0; k--) {
    runningSum = counting[arr[k] - min]
    result[runningSum - 1] = arr[k]
    counting[arr[k] - min]--
  }
  return result
}

console.log(countingSort(arr))