排序算法
算法分类
1
2
| 比较类排序: 通过比较来决定元素间的相对次序,由于其时间复杂度不能突破O(nlogn),也被称为非线性时间比较类排序
非比较类排序: 不通过比较来决定元素间的相对次序,它可以突破基于比较排序的时间下界,以线性时间运行,也被称为线性时间非比较类排序
|
| 排序算法 |
比较类排序 |
交换排序 |
冒泡排序 |
| 快速排序 |
| 插入排序 |
简单插入排序 |
| 希尔排序 |
| 选择排序 |
简单选择排序 |
| 堆排序 |
| 归并排序 |
二路归并排序 |
| 多路归并排序 |
| 非比较排序 |
计数排序 |
| 桶排序 |
| 基数排序 |
算法复杂度
| 排序方法 |
时间复杂度(平均) |
时间复杂度(最坏) |
时间复杂度(最好) |
空间复杂度 |
稳定性 |
| 插入排序 |
O(n²) |
O(n²) |
O(n) |
O(1) |
稳定 |
希尔排序 |
O(n¹•³) |
O(n²) |
O(n) |
O(1) |
不稳定 |
| 选择排序 |
O(n²) |
O(n²) |
O(n²) |
O(1) |
不稳定 |
| 堆排序 |
O(nlog₂n) |
O(nlog₂n) |
O(nlog₂n) |
O(1) |
不稳定 |
| 冒泡排序 |
O(n²) |
O(n²) |
O(n) |
O(1) |
稳定 |
| 快速排序 |
O(nlog₂n) |
O(n²) |
O(nlog₂n) |
O(nlog₂n) |
不稳定 |
| 归并排序 |
O(nlog₂n) |
O(nlog₂n) |
O(nlog₂n) |
O(n) |
稳定 |
| 计数排序 |
O(n+k) |
O(n+k) |
O(n+k) |
O(n+k) |
稳定 |
| 桶排序 |
O(n+k) |
O(n²) |
O(n) |
O(n+k) |
稳定 |
| 基数排序 |
O(n*k) |
O(n*k) |
O(n*k) |
O(n+k) |
稳定 |
## **相关概念**
1
2
3
4
| 稳定: 若a原本在b前面,而a=b,排序后a仍在b前面
不稳定: 若a原本在b前面,而a=b,排序后a可能出现在b后面
时间复杂度: 对排序数据的总的操作次数
空间复杂度: 指算法在计算机内执行时所需存储空间的度量,也是数据规模的函数
|
冒泡排序
依次比较相邻的两个元素,左边的元素若比右边的大,就将它俩的位置相互调换
动画演示
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| public static List<Integer> bubbleSort(Integer... i) {
int snap;
for (int j = 0; j < i.length; j++) {
for (int l = 0; l < i.length - 1; l++) {
if (i[l] > i[l + 1]) {
snap = i[l];
i[l] = i[l + 1];
i[l + 1] = snap;
}
}
}
return Arrays.asList(i);
}
|
选择排序
依次将从待排序的数组中选出最小的元素,将其放置到待排序的数组中的最左边
动画演示
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| public static List<Integer> selectSort(Integer... i) {
int snap,
t ;
for (int j = 0; j < i.length; j++) {
snap = j;
for (int l = snap + 1; l < i.length; l++)
if (i[snap] > i[l]) snap = l;
t = i[j];
i[j] = i[snap];
i[snap] = t;
}
return Arrays.asList(i);
}
|
快速排序
通过定位基准元素将待排序数组分成两部分,比关键字小和比关键字大的,再将这两部分通过递归达到有序排序的效果
动画演示
代码实现
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
| public static List<Integer> quickSort(Integer[] i) {
quickSort(i, 0, i.length - 1);
return Arrays.asList(i);
}
private static void quickSort(Integer[] i, Integer start, Integer end) {
if (start > end) return;
int datum = i[start],
j = start,
l = end,
temporary;
while (j < l) {
while (datum <= i[l] && j < l) l--;
while (datum >= i[j] && j < l) j++;
if (j < l) {
temporary = i[l];
i[l] = i[j];
i[j] = temporary;
}
}
i[start] = i[j];
i[j] = datum;
quickSort(i, start, j - 1);
quickSort(i, j + 1, end);
}
|
插入排序
从数组的索引1开始,将数组中待排序的元素按照升序规则插入到已排序好的数组中
动画实现
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| public static List<Integer> insertionSort(Integer... i) {
int temporary;
for (int j = 1; j < i.length; j++) {
for (int l = j; l > 0; l--) {
if (i[l] < i[l - 1]) {
temporary = i[l];
i[l] = i[l - 1];
i[l - 1] = temporary;
}
}
}
return Arrays.asList(i);
}
|
以下仅为动画演示,暂未进行研究
计数排序
动画演示
代码实现
基数排序
动画演示
代码实现
归并排序
动画演示
代码实现
堆排序
动画演示
代码实现
