学习计数排序可以了解到空间换时间的思想,其是一种牺牲空间换时间的排序算法,在其特定的场景上,甚至将时间复杂度降到了线性级别。
详细描述
计数排序作为一种线性时间复杂度的排序算法,其要求输入的数据必须是 有确定范围的整数,核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。
计数排序详细的执行步骤如下:
- 找出原数组中元素值最大的,记为
max
; - 创建一个新数组
count
,其长度是 max+1
,其元素默认值都为 0
; - 遍历原数组中的元素,以原数组中的元素作为
count
数组的索引,以原数组中的元素出现次数作为 count
数组的元素值; - 创建结果数组
result
,起始索引 index
; - 遍历
count
数组,找出其中元素值大于 0
的元素,将其对应的索引作为元素值填充到 result
数组中去,每处理一次,count
中的该元素值减 1
,直到该元素值不大于 0
,依次处理 count
中剩下的元素; - 返回结果数组
result
。
算法图解

问题解疑
计数排序的时间复杂度是多少?
计数排序的时间复杂度可以达到 $O(n+k)$,其中 k 是 count
数组的长度。
从这里可以知道,count
数组元素的取值越集中,算法耗费的时间越短。
计数排序有什么限制吗?
计数排序有两个前提需要满足:
- 排序的元素必须是整数,否则无法对应数组的索引下标
- 排序元素的取值要在一定范围内,并且比较集中,否则
count
数组将会非常大
只有这两个条件都满足,才能最大程度发挥计数排序的优势。
代码实现
排序接口
1
2
3
4
5
6
7
8
| package cn.fatedeity.algorithm.sort;
/**
* 排序接口
*/
public interface Sort {
int[] sort(int[] numbers);
}
|
排序抽象类
1
2
3
4
5
6
7
8
9
10
11
12
| package cn.fatedeity.algorithm.sort;
/**
* 排序抽象类
*/
public abstract class AbstractSort implements Sort {
protected void swap(int[] numbers, int src, int target) {
int temp = numbers[src];
numbers[src] = numbers[target];
numbers[target] = temp;
}
}
|
计数排序类
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
| package cn.fatedeity.algorithm.sort;
/**
* 计数排序类
*/
public class CountSort extends AbstractSort {
@Override
public int[] sort(int[] numbers) {
if (numbers.length <= 1) {
return numbers;
}
int min = numbers[0], max = numbers[0];
for (int number : numbers) {
if (number < min) {
min = number;
} else if (number > max) {
max = number;
}
}
int[] count = new int[max - min + 1];
for (int number : numbers) {
int index = number - min;
count[index]++;
}
int index = 0;
for (int i = 0; i < count.length; i++) {
while (count[i] > 0) {
numbers[index++] = i + min;
count[i]--;
}
}
return numbers;
}
}
|