CountingSort [计数排序]

# 介绍

计数排序（Counting sort）是一种稳定的线性时间排序算法。

# 原理

计数排序使用一个额外的数组 $C$ ，其中第 i 个元素是待排序数组 $A$ 中值等于 $i$ 的元素的个数。然后根据数组 $C$ 来将 $A$ 中的元素排到正确的位置。

由于用来计数的数组 C 的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上 1），这使得计数排序对于数据范围很大的数组，需要大量时间和内存。

算法的步骤如下：

找出待排序的数组中最大和最小的元素
统计数组中每个值为 $i$ 的元素出现的次数，存入数组 $C$ 的第 $i$ 项
对所有的计数累加（从 $C$ 中的第一个元素开始，每一项和前一项相加）
反向填充目标数组：将每个元素 $i$ 放在新数组的第 $C[i]$ 项，每放一个元素就将 $C[i]$ 减去 1

# 复杂度

平均时间复杂度 $O(n+k)$ 。
最坏时间复杂度 $O(n+k)$ 。
最优时间复杂度 $O(n+k)$ 。
空间复杂度 $O(n+k)$ 。

# 动画

# 实现

# JavaScript

/**
 * Counting sort is an algorithm for sorting a collection
 * of objects according to keys that are small integers.
 *
 * It is an integer sorting algorithm.
 *
 * Wikipedia: https://en.wikipedia.org/wiki/Counting_sort
 * Animated Visual: https://www.cs.usfca.edu/~galles/visualization/CountingSort.html
 */

const countingSort = (arr, min, max) => {
  // Create an auxiliary resultant array
  const res = []
  // Create and initialize the frequency[count] array
  const count = new Array(max - min + 1).fill(0)
  // Populate the freq array
  for (let i = 0; i < arr.length; i++) {
    count[arr[i] - min]++
  }
  // Create a prefix sum array out of the frequency[count] array
  count[0] -= 1
  for (let i = 1; i < count.length; i++) {
    count[i] += count[i - 1]
  }
  // Populate the result array using the prefix sum array
  for (let i = arr.length - 1; i >= 0; i--) {
    res[count[arr[i] - min]] = arr[i]
    count[arr[i] - min]--
  }
  return res
}

Array.prototype.countSort = function() {
  const C = []
  for(let i = 0; i < this.length; i++) {
    const j = this[i]
    C[j] >= 1 ? C[j] ++ : (C[j] = 1)
  }
  const D = []
  for(let j = 0; j < C.length; j++) {
    if(C[j]) {
      while(C[j] > 0) {
        D.push(j)
        C[j]--
      }
    }
  }
  return D
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

# 参考

编辑

上次更新: 2022/10/10, 21:03:42

← CombSort [梳排序] CycleSort [圈排序]→