计数排序过程分析

发表于 更新于 分类于 ， 本文字数： 344 阅读时长 ≈ 1 分钟

浅析过程

计数排序的原理是通过统计给定数组中，每个值出现的次数，最后通过统计后对应值出现的次数，从小到大返回一个新的数组。

代码实现思路

  1. 需要先计算出最大值及最小值获得该数组的区间，并通过大减小计算该数组最大可能长度，因为数组下标是从0开始，所以需要得出结果后加1。
  2. 定义一个空数组，用于统计出现次数。循环给定数值，通过 值 - 偏移量 = 下标 的公式，对空数组对应下标进行统计次数。
  3. 定义一个新数组用于保存排序后的结果。接着循环用于统计的数组，通过判断次数，并通过公式反推 下标 + 偏移量 = 值 将值添加到数组中。最终返回结果。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
const countSort = (arr) => {
  let max = 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 helper = new Array(max - min + 1)
  for(let i = 0; i < arr.length; i++) {
    const countValue = helper[arr[i] - min]
    helper[arr[i] - min] = countValue ? countValue + 1 : 1
  }
  const result = []
  for(let i = 0; i < helper.length; i++) {
    while(helper[i]){
      result.push(i + min)
      helper[i] -= 1
    }
  }
  return result
}

图例

image.png

画的有点丑，以上均是个人理解。如果有哪些不对的地方欢迎指出~