计数排序

非比较型排序，待排序集合键为整数，键的最大值为 K

遍历原数组，累计写入累计数组

图1-1

计数排序的第一步是在数数，比如数 6 有多少个，5 有多少个，3有多少个 ....

首先用一个指针 p 遍历原数组，先指向第一个元素 p = 0，在累计数组里计数 i = 6

图1-2

图1-3

p = 1 ; i = 5 :

图1-4

p = 2 ; i = 3:

注意：这里 i 跳过了 4

图1-5

图1-6

p = 3 ; i = 3:

图1-7

图1-8

p = 4 ; i = 2:

图1-9

图1-10

p = 5 ; i = 2:

图1-11

图1-12

p = 6 ; i = 1:

图1-13

图1-14

此时累计数组已经把所有的数都数完了即，1 有 1个，2 有 2个， 3 有 2个， 5 有1个，6 有1个。

接下来要加和累计数组，得到元素的位置。

将累计数组中前两项家和

i = 1 前两项值加和 0 + 1 = 1，即元素 1 应该写入结果数组中 1 - 1 = 0的位置。

图1-15

i = 2 时候，有 2 个 2，首先前两项加和即：1 + 2 = 3，那么 2 写入 3 - 1 = 2 的位置，因为有两个 2 ，所以需要写入结果数组中 1 和 2的位置

图1-16

i = 3 的时候， 前两项加和即 3 + 2 = 5，3 写入结果数组中 5 - 1 = 4 的位置。

图1-17

i = 4 的时候， 前两项加和即 5 + 0 = 5

图1-18

i = 5 的时候，前两项加和 5 + 1 = 6

图1-18

i = 6 的时候，前两项加和 6 + 1 = 7，元素组的 6 放入到结果数组中的 7 -1 的位置。

图1-19

此时，累计数组中就存放好了要放入结果数组中的位置。

图1-20

往结果数组中写入对应的值：

先遍历原数组中的第一个位置

p = 0 原数组中的值为 6，

i = 6 累计数组中的值为 7，

j = 6 结果数组中在第 7 - 1 = 6位写入值 6， 同时累计数组中减1，避免同时有好几个6的情况。

图1-21

图1-22

p = 1 原数组中的值为 5

i = 5 累计数组中存放的值为 6

j = 5 结果数组中在第 6 - 1 = 5 位置写入 5，同时累计数组中减1，避免同时有好几个5的情况。

图1-23

图1-24

p = 2 原数组中的值为 3

i = 3 累计数组中存放的值为 5

j = 4 结果数组中在 5 - 1 = 4 位置写入 3 ，同时累计数组中减1

图1-25

图1-25

p = 3 原数组中的值依然为 3

i = 3 累计数组中存放的值为 4

j = 3 结果数组中在 4 - 1 = 3 的位置写入 3，同时累计数组中减 1

图1-25

图1-25

p = 4 原数组中的值为 2

i = 2 累计数组中的值为 3

j = 2 结果数组中在 3 - 1 = 2 的位置写入 2 ，同时累计数组减 1

图1-25

图1-25

p = 5 原数组中的值为 2

i = 2 累计数组中的值为 2

j = 1 结果数组中在 2 - 1 = 1 的位置写入 2 ，同时累计数组减 1

图1-25

图1-25

p = 6 原数组中的值为 1

i = 1 累计数组中的值为 1

j = 0 结果数组中在 1 - 1 = 0 的位置写入 1 ，同时累计数组减 1

图1-25

图1-25

主要分三步骤：

• 遍历原数组得到累计数组
• 遍历累计数组加和
• 在通过遍历原数组写入结果数组

抽象

function counting_sort (A) {
  - A 需要排序的数组

  返回：结果数组
}

function counting_sort (A) {
  // 获取最大值
  const max = Math.max(...A)
  // 创建累计数组
  const B = Array(max + 1).fill(0)
  // 创建结果数组
  const C = Array(A.length)

  // 累计位递增，数数
  A.forEach((_, i) => B[A[i]]++)

  // 累计求和
  for (let i = 1; i < B.length; i++) {
    B[i] = B[i - 1] + B[i]
  }

  // 取出结果
  for (let i = 0; i < A.length; i++) {
    const p = B[A[i]] - 1 // 回写位置
    B[A[i]]-- // 减1后的新回写位置
    C[p] = A[i] // 回写结果
  }
  return C
}

console.log(counting_sort([5,4,3,3,2,2,1])) 
// [1, 2, 2, 3, 3, 4, 5]
console.log(counting_sort([19,8,3,2,5,4]))
// [2, 3, 4, 5, 8, 19]