封面画师：Nengoro(ネんごろぅ) 封面ID：74015476
本文参考视频：小马哥教育(SEEMYGO) 2019年 恋上数据结构与算法（第二季）
源码仓库：mofan212/data-structure-and-algorithm (github.com)
辅助学习网址：数据结构和算法动态可视化 Data Structure Visualizations
执行流程：本文统一以升序为例子。
0. 前言
之前介绍的冒泡、选择、插入、归并、快速、希尔、堆排序，都是基于比较的排序。
平均时间复杂度目前最低是 O(nlogn) 。
计数排序、桶排序、基数排序，都不是基于比较的排序。
它们是典型的用空间换时间，在某些时候，平均时间复杂度可以比 O(nlogn) 更低。
1. 计数排序
1.1 执行流程
计数排序（Counting Sort）于1954由 Harold H. Seward 提出，适合对一定范围内的整数进行排序。
计数排序的核心思想：统计每个整数在序列中出现的次数，进而推导出每个整数在有序序列中的索引。
计数排序动图演示：
1.2 简单实现
现有一个下图所示的序列，使用计数排序对其进行计数排序，则有：
编码实现
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
|
public class CountingSort extends Sort<Integer> {
@Override
protected void sort() {
int max = array[0];
for (int i = 0; i < array.length; i++) {
if (array[i] > max){
max = array[i];
}
}
int[] counts = new int[1 + max];
for (int i = 0; i < array.length; i++) {
counts[array[i]]++;
}
int index = 0;
for (int i = 0; i < counts.length; i++) {
while (counts[i]-- > 0){
array[index++] = i;
}
}
}
}
|
由于计数排序只能对整数进行排序，因此测试稳定性的方法isStable()就不能使用，但是我们可以对其进行改造。我们可以分析出当前写法的计数排序是不稳定的，那么isStable()方法改写为：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| private boolean isStable() {
if (this instanceof SelectionSort) return false;
if (this instanceof ShellSort) return false;
if (this instanceof CountingSort) return false;
Student[] students = new Student[20];
for (int i = 0; i < students.length; i++) {
students[i] = new Student(i * 10, 10);
}
sort(((E[]) students));
for (int i = 1; i < students.length; i++) {
int score = students[i].score;
int prevScore = students[i - 1].score;
if (score != prevScore + 10) return false;
}
return true;
}
|
我们测试一下，使用序列{7, 3, 5, 8, 6, 7, 4, 5}进行测试并打印出排序结果：
虽然这种方法可以实现计数排序，但是这样的实现存在以下问题：
- 无法对负整数进行排序
- 极其浪费内存空间
- 当前写法是一个不稳定的排序
1.3 改进思路
在简单实现中，计数排序存在大量的问题，我们需要对其进行改进。
改进图解如下：
假设 array 中的最小值是 min，则有：
比如：
- 元素 8 在有序序列中的索引为 counts[8 - 3] - 1 = 7
- 倒数第一个元素 7 在有序序列中的索引为 counts[7 - 3] - 1 = 6
- 倒数第二个元素 7 在有序序列中的索引为 counts[7 - 3] - 2 = 5
改进后排序思路
第一步：
第二步：
第三步：
第四步：
第五步：
概括一下：
1、创建 counts ，确定索引与索引对应的值（ 重点！ ）
2、创建一个和 array 容量相同的空数组
3、从右向左遍历 array 数组，利用 counts 计算每次遍历的值在有序数组中的索引，并在counts 将遍历的值对应的次数减一，最后将遍历结果填入有序数组中
利用这种改进的方式，可以让计数排序能够处理负整数，节约了内存空间，同时也让计数排序成为了稳定性的排序。
编码实现
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
| public class CountingSort extends Sort<Integer> {
@Override
protected void sort() {
int max = array[0];
int min = array[0];
for (int i = 0; i < array.length; i++) {
if (array[i] > max) {
max = array[i];
}
if (array[i] < min) {
min = array[i];
}
}
int[] counts = new int[max - min + 1];
for (int i = 0; i < array.length; i++) {
counts[array[i] - min]++;
}
for (int i = 1; i < counts.length; i++) {
counts[i] += counts[i - 1];
}
int[] newArray = new int[array.length];
for (int i = array.length - 1; i >= 0; i--) {
newArray[--counts[array[i] - min]] = array[i];
}
for (int i = 0; i < newArray.length; i++) {
array[i] = newArray[i];
}
}
}
|
改进后的计数排序是稳定的排序，我们再次修改isStable()方法：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| private boolean isStable() {
if (this instanceof SelectionSort) return false;
if (this instanceof ShellSort) return false;
if (this instanceof CountingSort) return true;
Student[] students = new Student[20];
for (int i = 0; i < students.length; i++) {
students[i] = new Student(i * 10, 10);
}
sort(((E[]) students));
for (int i = 1; i < students.length; i++) {
int score = students[i].score;
int prevScore = students[i - 1].score;
if (score != prevScore + 10) return false;
}
return true;
}
|
我们测试一下，使用序列{7, 3, 5, 8, 6, 7, 4, 5}进行测试并打印出排序结果：
1.4 复杂度分析
最好、最坏、平均时间复杂度为： O(n + k)
空间复杂度为： O(n + k)
其中， k 表示整数的取值范围
改进后的计数排序属于稳定排序。
拓展思考
我们最开始介绍计数排序时就说明了计数排序只能对一定范围内的整数进行排序，那么是不是说对于自定义类型就真的毫无办法？
其实也不是，如果自定义对象可以提供用以排序的整数类型 ，依然可以使用计数排序。
比如下图所示的部分代码：
2. 基数排序
基数排序（Radix Sort），基数排序的发明可以追溯到 1887 年赫尔曼·何乐礼（Herman Hollerith）在打孔卡片制表机（Tabulation Machine）上的贡献，而打孔卡片制表机是电脑的前身。何乐礼被广泛认为是现代机械数据处理之父。
2.1 执行流程
基数排序非常适合用于整数排序（尤其是非负整数），本文也只演示对非负整数进行基数排序。
执行流程： 依次对个位数、十位数、百位数、千位数、万位数…进行排序（从低位到高位，不能反过来），高位不存在以 0 替代。
基数排序执行流程图：
一个小细节
我们使用基数排序时，会依次对个位数、十位数、百位数…（从低位到高位）进行排序，又因为我们使用的是十进制数，那么个位数、十位数、百位数等位数的取值范围都是固定的 0 ~ 9 。
上文说到，计数排序可以对一定范围内的整数进行排序，那么可以使用计数排序对基数排序中位数的排序进行排序。
2.2 编码实现
根据前文的分析，可以编写如下代码：
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
50
51
| package com.yang.sort;
public class RadixSort extends Sort<Integer> {
@Override
protected void sort() {
int max = array[0];
for (int i = 0; i < array.length; i++) {
if (array[i] > max) {
max = array[i];
}
}
for (int divider = 1; divider < max; divider++) {
countingSort(divider);
}
}
protected void countingSort(int divider) {
int[] counts = new int[10];
for (int i = 0; i < array.length; i++) {
counts[array[i] / divider % 10]++;
}
for (int i = 1; i < counts.length; i++) {
counts[i] += counts[i - 1];
}
int[] newArray = new int[array.length];
for (int i = array.length - 1; i >= 0; i--) {
newArray[--counts[array[i] / divider % 10]] = array[i];
}
for (int i = 0; i < newArray.length; i++) {
array[i] = newArray[i];
}
}
}
|
由于基数排序的内部采用了计数排序，因此基数排序也是稳定的。
修改isStable()方法：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| private boolean isStable() {
if (this instanceof SelectionSort) return false;
if (this instanceof ShellSort) return false;
if (this instanceof CountingSort) return true;
if (this instanceof RadixSort) return true;
Student[] students = new Student[20];
for (int i = 0; i < students.length; i++) {
students[i] = new Student(i * 10, 10);
}
sort(((E[]) students));
for (int i = 1; i < students.length; i++) {
int score = students[i].score;
int prevScore = students[i - 1].score;
if (score != prevScore + 10) return false;
}
return true;
}
|
我们测试一下，生成 10 个随机数，范围[1, 30000]进行测试并打印出排序结果：
2.3 复杂度
最好、最坏、平均时间复杂度为：O(d * (n + k)) ，d 是最大值的位数， k 是进制。
基数排序属于稳定排序。
空间复杂度： O(n + k)，k 是进制。
2.4 其他思路
我们可以用二维数组来实现基数排序。
图解：
设待排序列的数据规模是 n ，那么二维数组的行数也为 n。
3. 桶排序
桶排序（Bucket Sort）。
执行流程
1、创建一定数量的桶（比如用数组、链表作为桶）
2、按照一定的规则（不同类型的数据，规则不同），将序列中的元素均匀分配到对应的桶
3、分别对每个桶进行单独排序
4、将所有非空桶的元素合并成有序序列
假设我们一组数据全为小于 1 的正小数进行排序， 设置桶数量为 8 个，元素在桶中的索引为： 元素值 * 元素数量，那么则有：
桶排序的实现
复杂度与稳定性
桶排序可以编写成稳定性的排序方法。
