logo

排序算法之计数排序,桶排序,基数排序

计数排序(Counting Sort)

计数排序不是比较排序,而是利用一个额外的数据记录数组下标 $i$ 对应的值出现的次数,再通过记录来排序数值,因此只适用于 $0\sim{k}$ 之间的整数排序。其性能理论上优于比较排序算法。

计数排序

步骤(升序)

  1. 找出等待排序序列中的最大值 $max$ 和 最小值 $min$,创建一个长度为 $max-min+1$的数组 $C$
  2. 统计数组中每个值为 $x$ 的元素出现次数,存入数组 $C$ 的第 $x-min$ 项
  3. 遍历数组 $C$ 按统计结果次数填充原序列,填充值为 $i+min$。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function countSort(arr) {
let max = Math.max.apply(null, arr);
let min = Math.min.apply(null, arr);
let C = [];
let len = arr.length;
/* 统计元素 */
for (let i = 0; i < len; i++) {
C[i - min] ? C[i - min]++ : (C[i - min] = 1);
}
/* 填充数组 */
arr.length = 0;
for (let j = 0; j < max - min + 1; j++) {
/* 保证稳定性 */
let count = 0;
while (C[j] && count < C[j]) {
arr.push(j + min);
count++;
}
}
return arr;
}

分析

计数排序复杂度是线性的,影响因素为序列元素值的区间范围和序列长度,对于值区间为 $k$,长度为 ${n}$ 的序列:
空间复杂度:$O(k)$
时间复杂度:$O(n+k)$
Out-Place 排序,相同元素位置固定,稳定排序。

桶/箱排序(Buckets Sort)

桶排序主要是通过对元素进行分组并排序,融合了分治法的思想,减少比较次数,提升算法效率。

箱排序

步骤

  1. 创建一定数量的空桶。
  2. 对序列元素按桶的区间分到不同的桶。
  3. 对不是空桶的桶进行排序
  4. 合并所有不为空的桶得出排序结果。

实现

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
function bucketSort(arr, bucketsNum = 10) {
/* 使用插入排序进行排序 */
function insertionSort(array) {
for (let i = 1, len = array.length; i < len; i++) {
let j = i;
while (array[j] <= array[j - 1] && j > 0) {
let temp = array[j];
array[j] = array[j - 1];
array[j - 1] = temp;
j--;
}
}
return array;
}
/* 根据桶数量划分每个桶的大小 */
const len = arr.length;
const max = Math.max(...arr);
const min = Math.min(...arr);
const buckets = [];
const bucketSize = Math.floor((max - min) / bucketsNum) + 1;
/* 遍历元素分到不同的桶 */
for (let i = 0; i < len; i++) {
const index = Math.floor(arr[i] / bucketSize);
if (buckets[index]) {
buckets[index].push(arr[i]);
} else {
buckets[index] = [arr[i]];
}
}
/* 对每个桶进行排序 */
for (let j = 0, blen = buckets.length; j < blen; j++) {
buckets[j] && insertionSort(buckets[j]);
}
/* 重置数组 */
arr.length = 0;
/* 将桶中元素按序倒入arr */
for (let k = 0, blen = buckets.length; k < blen; k++) {
if (buckets[k]) {
arr.push(...buckets[k]);
}
}

return arr;
}

分析

桶排序对于值区间为 $k$,长度为 ${n}$ 的序列:
空间复杂度:桶个数为 $k$ 时切使用排序算法空间复杂度为 $O(1)$ 时,空间复杂度 $O(n+k)$
时间复杂度:当桶大小为 $1$ 时,时间复杂度 $O(n+k)$,不为 $1$ 时随内部使用的排序算而变化。
Out-Place 排序,相同元素位置固定,稳定排序。

基数排序(Radix Sort)

基数排序也是一种非比较排序,通过对关键字拆解。对于数值关键字,从低位比较到高位,从而达到排序的效果,如下图:

基数排序

步骤(升序)

这里实现对数值基数排序:

  1. 创建标识为 $0\sim9$ 的”桶”,最大数位数为 $k$
  2. 从个位开始比较,如果对应位数不存在则视为 $0$,依次将元素放入桶中。
  3. 从标识为零开始的依次将桶中序列元素依次排列填充为新的待排序序列
  4. 重复 2,3 步骤 $k$ 轮,得到有序序列。

实现

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
function radixSort(arr) {
/* 获取数值对应位数的数字 */
let getDigit = (num, offset) => {
let len = String(num).length;
return String(num)[len - 1 - offset] || 0;
};
let max = Math.max(...arr);
/* 最大数的位数 */
let digitLength = String(max).length;
let buckets = [];
/* 遍历最大数位数 */
for (let i = 0; i < digitLength; i++) {
/* 每次遍历清空桶 */
buckets.length = 0;
/* 遍历排序序列,依次放入桶中 */
for (let j = 0, arrLen = arr.length; j < arrLen; j++) {
let currentNum = getDigit(arr[j], i);
if (buckets[currentNum]) {
buckets[currentNum].push(arr[j]);
} else {
buckets[currentNum] = [arr[j]];
}
}
/* 清空arr */
arr.length = 0;
/* 将桶中元素按序倒入arr */
for (let k = 0, len = buckets.length; k < len; k++) {
if (buckets[k]) {
arr.push(...buckets[k]);
}
}
}
return arr;
}

分析

桶排序对于关键个数为 $k$,长度为 ${n}$ 的序列,对于数值,$k$值等于序列出现不同数字的个数:
空间复杂度:空间复杂度为 $O(n+k)$,需要 $k$ 个桶存 $n$ 个元素
时间复杂度:外层遍历 $k$ 次,内层遍历 $n$ 次,时间复杂度为 $O(k*n)$
Out-Place 排序,相同元素位置固定,稳定排序。

总结

以上三种线性,非比较排序方式通过增加空间复杂度来降低时间复杂度。再特定情况下性能会优于比较排序。这里的实现只能用于自然数排序,再特定情况我们可以考虑使用这几种排序方法以及改进。

Chorme72 性能测试

10000 个数测试代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function test(time) {
let tempTime = time;
let result = [];
while (time > 0) {
var n = 10000;
var arr = Array.from({
length: n
}).map(() => Math.round(Math.random() * n));

var start, end;
start = performance.now();

SortMethod();

end = performance.now();
result.push(end - start);
time--;
}
return result.reduce((a, b) => a + b) / tempTime;
}
test(10);
排序方法10 次平均时间(ms)
计数排序3.260ms
桶排序26.609ms
基数排序5.328ms

这里我们会发现这三种排序方法优于普通的排序算法,但是需要额外的空间。虽然可能由于实现不同产生偏差,在大体上性能仍然比不上快速排序,希尔排序。

综合比较

对于上述算法实现来说,算法复杂度如下:

排序方法平均时间复杂度最佳时间复杂度最差时间复杂度空间复杂度稳定性排序方式
计数排序$O(n+k)$$O(n+k)$$O(n+k)$$O(k)$不稳定In-Place
桶排序$O(n+k)$$O(n+k)$$O(n^2)$$O(k+n)$不稳定In-Place
基数排序$O(k*n)$$O(k*n)$$O(k*n)$$O(k+n)$稳定Out-Place

参考链接