算法:排序


四月的第四周,来整理排序算法,本篇文章基于 CS-Notes 的《算法-排序》,那篇文章的代码写得非常通用,使用泛型并继承 Comparable 接口来进行,本篇只针对数字做排序,重点放在算法而不是兼容上。

算法写完这一篇就暂时不写了,每天细水长流做一做题,多积累一点算法底蕴再抽空回来写。


总结写在最前面,方便查看。本篇文章涉及七种排序算法(以及几种亚种),时间和空间复杂度的对比汇总如下:

算法 稳定性 时间复杂度 空间复杂度
选择排序 × 1
冒泡排序 1
插入排序 N ~ N² 1
希尔排序 × N 的若干倍乘于递增序列的长度 1
归并排序 NlogN N
快速排序 × NlogN logN
堆排序 × NlogN 1

P.S. 稳定性的意思是,相同项排序前后不能调换位置,例如 1、[2]、(2)、3 排序后不能变成 1、(2)、[2]、3。


选择排序

遍历最小的交换

选择排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int[] selectSort(int[] nums) {
int n = nums.length;
// 从第一个开始,执行到倒数第二个
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (nums[minIndex] > nums[j]) {
minIndex = j;
}
}
swap(nums, i, minIndex);
}
return nums;
}

冒泡排序

相邻比较,最小的升到最前面

冒泡排序(这个 gif 是反过来的,最大的挪到最后)

1
2
3
4
5
6
7
8
9
10
11
12
public int[] bubbleSort(int[] nums) {
int n = nums.length;
for (int i = 0; i < n; i++) {
// 从倒数第一个开始,执行到第i+1个
for (int j = n - 1; j > i; j--) {
if (nums[j] < nums[j - 1]) {
swap(nums, j, j - 1);
}
}
}
return nums;
}

插入排序

每个数字一路往前交换,等效为插入

插入排序

1
2
3
4
5
6
7
8
9
10
public int[] insertSort(int[] nums) {
int n = nums.length;
for (int i = 1; i < n; i++) {
// 从第二个开始,每个数字一路往前交换,直到前面比它小为止
for (int j = i; j > 0 && nums[j] < nums[j - 1]; j--) {
swap(nums, j, j - 1);
}
}
return nums;
}

希尔排序

改进的插入排序,设置了间隔

希尔排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int[] shellSort(int[] nums) {
int n = nums.length;

// 间隔数量,初始值为[1, 4, 13, 40……]数列中最接近n的那个
int h = 1;
while (h < n / 3) {
h = 3 * h + 1;
}

while (h >= 1) {
for (int i = h; i < n; i++) {
// 从第h+1个开始,每个数字一路往前交换(间隔为h),直到前面比它小为止
for (int j = i; j >= h && nums[j] < nums[j - h]; j--) {
swap(nums, j, j - h);
}
}
h /= 3;
}

return nums;
}

归并排序

将数组分成两个子数组,分别排序,再合并

归并排序

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
private int[] helpArray;

public int[] mergeSort(int[] nums) {
helpArray = new int[nums.length];
return doMergeSort(nums, 0, nums.length - 1);
}

private int[] doMergeSort(int[] nums, int l, int h) {
if (l < h) {
int mid = l + (h - l) / 2;
doMergeSort(nums, l, mid);
doMergeSort(nums, mid + 1, h);
merge(nums, l, h, mid);
}
return nums;
}

private void merge(int[] nums, int l, int h, int mid) {
// 技巧:用辅助数组
System.arraycopy(nums, l, helpArray, l, h - l + 1);
int i = l, j = mid + 1, curr = l;
while (curr <= h) {
if (i <= mid && j <= h) {
if (helpArray[i] <= helpArray[j]) {
nums[curr++] = helpArray[i++];
} else {
nums[curr++] = helpArray[j++];
}
} else if (i <= mid) {
nums[curr++] = helpArray[i++];
} else {
nums[curr++] = helpArray[j++];
}
}
}

快速排序

让某数左边都是小于等于它的数,右边都是大于等于它的数,再二分递归

快排

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
public int[] quickSort(int[] nums) {
doQuickSort(nums, 0, nums.length - 1);
return nums;
}

private void doQuickSort(int[] nums, int l, int h) {
if (l < h) {
// mid左边都是小于等于它的数字,右边都是大于等于它的数字
int mid = partition(nums, l, h);
doQuickSort(nums, l, mid - 1);
doQuickSort(nums, mid + 1, h);
}
}

private int partition(int[] nums, int l, int h) {
// 取第一个数作为比较基础
int target = nums[l];
int i = l, j = h + 1;
while (i < j) {
// 左 -> 右 找更大的数
while (++i != h && nums[i] < target) ;
// 左 <- 右 找更小的数
while (--j != l && nums[j] > target) ;
if (i < j) {
swap(nums, i, j);
}
}
// 此时 i>j 要跟坐标小的交换,并返回这个小坐标
swap(nums, l, j);
return j;
}

堆排序

数组中坐标 2k 和 2k+1 的数字,是 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
public int[] heapSort(int[] nums) {
int n = nums.length - 1;
for (int i = n / 2; i >= 1; i--) {
// 从倒数第二层预排一次,大顶堆
sink(nums, i, n);
}

while (n > 1) {
// 最大的数交换到数组尾,将交换来的数再大顶堆下沉
swap(nums, 1, n--);
sink(nums, 1, n);
}
return nums;
}

private void sink(int[] nums, int parent, int n) {
while (parent * 2 <= n) {
int son = parent * 2;
if (son < n && nums[son] < nums[son + 1]) {
son++;
}
// 父亲一定比孩子大,排到某层符合就不用排了
if (nums[parent] >= nums[son]) {
break;
}
swap(nums, parent, son);
parent = son;
}
}

整理完算法,顺便学习一下 Java 默认提供的一些排序 API。

Comparable & Comparator

Java 排序相关的内容,最常用到的就是 Comparable 和 Comparator,这两个都是接口类。

Java 对容器、数组进行排序时调用的 sort() 方法(例如 Collections.sort(list)Arrays.sort(array))时,要不然让容器内的元素实现 Comparable 接口,要不然自己重写 Comparator 接口说明排序逻辑。知乎文章《Java 中的排序》对此解释得清晰明了:

  • 如果一个类实现了 Comparable 接口,那么它“天生”就是可以借助 Collections、Arrays、SortedMap、SortedSet 等类来进行排序。

  • 但是,如果一个类没有实现 Comparable 接口,却也想利用 Collections、Arrays、SortedMap、SortedSet 等来进行排序,就可以通过指定一个自定义的 Comparator 来实现。

如果觉得两个接口容易记混,可以思忖一下名字,一个叫做 Comparable(可以比较),表明实现该接口的类是可以进行比较的,另一个叫做 Comparator(比较器),表明该接口是用来确定比较大小逻辑的。

具体使用逻辑懒得写了,看看之后有没有写的动力吧……