经典排序算法
引言
最近参加了 Datawhale 的算法打卡活动，感觉自己还是很多不足。决定翻开吃灰的《算法3》。重新学习下算法，加深下记忆。
导航
冒泡排序
冒泡排序（Bubble Sort）是一种简单的排序算法。由于在算法的执行过程中，较小的元素像汽包般慢慢 浮 到数列的顶端，故称为冒泡排序。
工作原理
每次检查相邻两个元素，如果前面的元素与后面的元素满足给定的排序条件，就将相邻两个元素交换，当没有相邻的元素需要交换时，排序就完成了。
经过 i 次扫描后，数列的末尾 i 项必定是最大的 i 项，因此冒泡排序最多需要扫描 n - 1 遍数组就能完成排序。
性质
稳定的排序方法。（稳定排序意思就是排序之前和排序之后位置不变。比如 1 3 3 1 这样的数组，位置 i = 2 时，3 怎么交换都在原来位置）
时间复杂度
- 序列完全有序，时间复杂度 O(n)
- 最坏情况下需要执行 (n - 1) * n / 2 次交换，时间复杂度 O(n²)
- 平均情况下，时间复杂度 O(n²)
空间复杂度
在原来的数列完成，需要一个辅助空间，故空间复杂度 O(1)。
代码实现
实现一
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
private static void bubbleSort(int[] arr) {
int temp;
for (int i = 0; i < arr.length - 1; i++) {
boolean flag = false;
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
flag = true;
}
}
if (!flag) {
break;
}
}
}
实现二
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
private static void bubbleSort(int[] arr) {
int temp;
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr.length; j++) {
if (arr[i] < arr[j]) {
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
}
效果
选择排序
选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。
工作原理
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
性质
由于 swap（交换两个元素）操作的存在，选择排序是一个不稳定排序。
时间复杂度
- 平均时间复杂度 О(n²)
- 最坏时间复杂度 О(n²)
- 最优时间复杂度 О(n²)
空间复杂度
和冒泡排序一样，都是在同一个序列完成，需要一个辅助空间，故空间复杂度 O(1)。
实现代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
private static void selectionSort(int[] arr) {
int min;
for (int i = 0; i < arr.length - 1; i++) {
min = i;
// 找到比当前更小的值，如果想从大到小，则找最大值
for (int j = i; j < arr.length; j++) {
if (arr[min] > arr[j]) {
// 记录下标
min = j;
}
}
if (i != min) {
int temp = arr[i];
arr[i] = arr[min];
arr[min] = temp;
}
}
}
效果
插入排序
插入排序不如前面两个排序简单，但是和扑克牌差不多，就是发下来是乱的，需要你直接插到对应位置。
工作原理
将待排列元素划分为“已排序”和“未排序”两部分，每次从“未排序的”元素中选择一个插入到“已排序的”元素中的正确位置。
一个与插入排序相同的操作是打扑克牌时，从牌桌上抓一张牌，按牌面大小插到手牌后，再抓下一张牌。
性质
是一个稳定排序。
时间复杂度
- 平均时间复杂度 О(n²)
- 最坏时间复杂度 О(n²)
- 最优时间复杂度 О(n)
空间复杂度
需要辅助空间 O(1)
实现代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
private static void insertSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int temp = arr[i];
int j = i;
while (j > 0 && temp < arr[j - 1]) {
// 往后一位
arr[j] = arr[j - 1];
// 找到合适位置
j--;
}
if (j != i) {
// 交换位置
arr[j] = temp;
}
}
}
效果
归并排序
归并排序是一种采用了分治思想的排序算法。
工作原理
采用分治法:
- 分割：递归地把当前序列平均分割成两半。
- 集成：在保持元素顺序的同时将上一步得到的子序列集成到一起（归并）。
性质
稳定排序
时间复杂度
- 平均时间复杂度 O(nlog n)
- 最坏时间复杂度 O(nlog n)
- 最优时间复杂度 O(nlog n)
空间复杂度
需要额外的数组空间，故 O(n)
实现代码
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
private static void sort(int[] arr, int low, int high) {
int mid = (low + high) / 2;
if (low < high) {
sort(arr, low, mid);
sort(arr, mid + 1, high);
merge(arr,low, mid, high);
}
}
private static void merge(int[] arr, int low, int mid, int high) {
int[] temp = new int[high + 1 - low];
int i = low;
int j = mid + 1;
int k = 0;
while (i <= mid && j <= high) {
if (arr[i] < arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
}
}
while (i <= mid) {
temp[k++] = arr[i++];
}
while (j <= high) {
temp[k++] = arr[j++];
}
if (temp.length >= 0) {
System.arraycopy(temp, 0, arr, low, temp.length);
}
}
效果
快速排序
快速排序（英语：Quicksort），又称分区交换排序（partition-exchange sort），简称快排，是一种被广泛运用的排序算法。
工作原理
快速排序的工作原理是通过 分治 的方式来将一个数组排序。
快速排序分为三个过程：
- 将数列划分为两部分（要求保证相对大小关系）；
- 递归到两个子序列中分别进行快速排序；
- 不用合并，因为此时数列已经完全有序。
和归并排序不同，第一步并不是直接分成前后两个序列，而是在分的过程中要保证相对大小关系。具体来说，第一步要是要把数列分成两个部分，然后保证前一个子数列中的数都小于后一个子数列中的数。为了保证平均时间复杂度，一般是随机选择一个数 来当做两个子数列的分界。
之后，维护一前一后两个指针 和 ，依次考虑当前的数是否放在了应该放的位置（前还是后）。如果当前的数没放对，比如说如果后面的指针 遇到了一个比 小的数，那么可以交换 和 位置上的数，再把 向后移一位。当前的数的位置全放对后，再移动指针继续处理，直到两个指针相遇。
其实，快速排序没有指定应如何具体实现第一步，不论是选择 的过程还是划分的过程，都有不止一种实现方法。
第三步中的序列已经分别有序且第一个序列中的数都小于第二个数，所以直接拼接起来就好了。
性质
不稳定排序
时间复杂度
- 平均时间复杂度 O(nlogn)
- 最坏时间复杂度 O(n²)
- 最优时间复杂度 O(nlogn)
空间复杂度
根据事先的方式不同而不同
实现代码
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
private static void quickSort(int[] arr, int low, int high) {
if (low >= high) {
return;
}
int p = arr[low];
int i = low;
int j = high;
int temp;
while (i < j) {
while (arr[j] >= p && i < j) {
j--;
}
while (arr[i] <= p && i < j){
i++;
}
temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
}
arr[low] = arr[i];
arr[i] = p;
quickSort(arr, low, j-1);
quickSort(arr, j+1, high);
}
效果
基数排序
基数排序（Radix Sort）是一种非比较型的排序算法，最早用于解决卡片排序的问题。
工作原理
将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。
性质
稳定排序
时间复杂度
- 最坏时间复杂度 O(kN)
空间复杂度
需要 k 个 桶，故需要 O(k + O)
实现代码
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
private static void radixSort(int[] arr) {
int max = arr[0];
int exp;
for (int anArr : arr) {
if (anArr > max) {
max = anArr;
}
}
for (exp = 1; max / exp > 0; exp *= 10) {
int[] temp = new int[arr.length];
int[] buckets = new int[10];
for (int value : arr) {
buckets[(value / exp) % 10]++;
}
for (int i = 1; i < buckets.length; i++) {
buckets[i] += buckets[i - 1];
}
for (int i = arr.length - 1; i >= 0; i--) {
temp[buckets[(arr[i] / exp) % 10] - 1] = arr[i];
buckets[(arr[i] / exp) % 10]--;
}
System.arraycopy(temp, 0, arr,0, arr.length);
}
}
效果
总结
| 排序算法 | 平均时间复杂度 | 最坏时间复杂度 | 最好时间复杂度 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(n²) | O(n) | O(1) | 稳定 |
| 基数排序 | O(kN) | O(kN) | O(kN) | O(k + O) | 稳定 |
| 归并排序 | O(nlog n) | O(nlog n) | O(nlog n) | O(n) | 稳定 |
| 快速排序 | O(nlog n | O(n²) | O(nlog n | 根据具体实现不同 | 不稳定 |
| 插入排序 | O(n²) | O(n²) | O(n) | O(1) | 稳定 |
| 选择排序 | O(n²) | O(n²) | O(n²) | O(1) | 不稳定 |
声明
作者: Sinsy
本文链接：https://blog.sincehub.cn/2020/09/24/classic-sort/
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文声明。
如您有任何商业合作或者授权方面的协商，请给我留言：550569627@qq.com
引用
- [1] OI Wiki 排序
- [2] VisuAlgo 排序可视化
- [3] 维基百科，自由的百科全书 - 维基百科
