经典排序算法
引言
最近参加了 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] 维基百科,自由的百科全书 - 维基百科