排序算法总结与 Java 实现
O(n^2) 排序算法
-
基础，编码简单，易于实现，是一些简单情景的首选
-
在一些特殊情况下，简单的排序算法更有效
-
简单的排序算法思想衍生出复杂的排序算法
-
作为子进程，改进更复杂的排序算法
冒泡排序（Bubble Sort）
对相邻的元素进行两两比较，顺序相反则进行交换，这样每一趟会将最小或最大的元素「浮」到顶端，最终达到完全有序
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
/**
* 冒泡排序，不断找出最大值
* @param arr
*/
public static void bubbleSort(int[] arr) {
int len = arr.length;
for (int i = 0; i < len - 1; i++) {
for (int j = 0; j < len - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr, j, j + 1);
}
}
}
}
/**
* 冒泡排序优化：假定有序，减少趟数
* @param arr
*/
public static void bubbleSort2(int[] arr) {
boolean isSorted = true; // 假定有序
int len = arr.length;
for (int i = 0; i < len - 1; i++) {
isSorted = true;
for (int j = 0; j < len - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr, j, j + 1);
isSorted = false; // 存在交换则无序
}
}
if (isSorted) { // 假定有序，减少趟数
break;
}
}
}
/**
* 交换
*
* @param arr
* @param i
* @param j
*/
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
选择排序（Selection Sort）
不断在后面的数组找到最小的元素，放在前面排序好的数组，依次类推，最终达到完全有序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
* 选择排序
* @param arr
*/
public static void selectionSort(int[] arr) {
int len = arr.length;
for (int i = 0; i < len - 1; i++) {
// 假定当前为最小值，减少趟数
int min = i;
for (int j = i + 1; j < len; j++) {
if (arr[j] < arr[min]) {
min = j;
}
}
if (min != i) {
swap(arr, i, min);
}
}
}
插入排序（Insertion Sort）
依次遍历后面的数组，与前面的数组进行比较，直到找到比前面数组中元素大的位置，插入即可
优化
不用每次比较时都交换，暂时保存后面数组的数据，前面数组在往前遍历时，前一个值赋值给后一个，直到后面数组的数据找到合适的位置（即前面数组中前一个值 <= 当前值）
对于近乎有序的数组，速度非常快，应用：系统日志
对于有序数组，复杂度为 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
/**
* 插入排序
* @param arr
*/
public static void insertionSort(int[] arr) {
int len = arr.length;
for (int i = 1; i < len; i++) {
for (int j = i; j > 0; j--) {
if (arr[j] < arr[j - 1]) {
swap(arr, j, j - 1);
} else {
break;
}
}
}
}
/**
* 插入排序优化：不用每次比较时都交换，暂时保存后面数组的数据，前面数组在往前遍历时，前一个值赋值给后一个，直到后面数组的数据找到合适的位置（即前面数组中前一个值 <= 当前值）
* @param arr
*/
public static void insertionSort2(int[] arr) {
int len = arr.length;
for (int i = 1; i < len; i++) {
int temp = arr[i];
int j = i - 1;
for (; j >= 0 && arr[j] > temp; j--) {
arr[j + 1] = arr[j];
}
arr[j + 1] = temp;
}
}
希尔排序（Shell Sort）
希尔排序（Shellsort），也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。
希尔排序是基于插入排序的以下两点性质而提出改进方法的：
- 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率
- 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位
插入排序的延伸，插入排序每次都和之前的一个元素进行比较。希尔排序每一次都和之前第 h 元素进行比较，将 h -> 1，即排序完成
时间复杂度：O(n^3/2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
* 希尔排序
* @param arr
*/
public static void shellSort(int[] arr) {
int len = arr.length;
for (int step = len / 2; step >= 1; step /= 2) {
for (int i = step; i < len; i++) {
int temp = arr[i];
int j = i - step;
// 插入排序
for (; j >= 0 && arr[j] > temp; j -= step) {
arr[j + step] = arr[j];
}
arr[j+ step] = temp;
}
}
}
O(nlogn) 排序算法
归并排序（Merge Sort）
自顶向下的归并排序
先把数组以一半依次划分，直到不能划分为止，然后依次向上进行归并，归并成一个数组时，即排序完成
归并过程（Merge）
- 使用临时空间
T，待归并数组A、B（逻辑上分为 A、B，其实是一个数组） - 界限：
l(left)、m(middle)、r(right)、A[l...m]、B[m+1...r] A[i]和B[j]依次比较大小，小的元素添加到T[k]，添加完成即排序完成
优化
- 归并操作之前判断
arr[mid] > arr[mid+1]，mid之前的数组和mid之后的数组都是有序的，如果arr[mid] <= arr[mid+1]，说明当前是有序的 - 递归操作到底时，在数据量较小时，可以选择插入排序，数据量越小，有序的可能性越大
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
/**
* 归并排序，递归版
*
* @param arr
*/
public static void mergeSort(int[] arr) {
int len = arr.length;
mergeSort(arr, 0, len - 1);
}
// 递归使用归并排序，对 arr[l...r] 的范围进行排序
private static void mergeSort(int[] arr, int l, int r) {
if (l >= r) {
return;
}
int mid = (l + r) / 2;
mergeSort(arr, l, mid);
mergeSort(arr, mid + 1, r);
// 对于arr[mid] <= arr[mid+1]的情况,不进行merge
// 对于近乎有序的数组非常有效,但是对于一般情况,有一定的性能损失
if (arr[mid] > arr[mid + 1]) {
merge(arr, l, mid, r);
}
}
// 将 arr[l...mid] 和 arr[mid+1...r] 进行归并
private static void merge(int[] arr, int l, int mid, int r) {
int[] aux = Arrays.copyOfRange(arr, l, r + 1);
// 初始化，i 指向左半部分的起始索引位置 l，j 指向右半部分起始索引位置 mid+1
int i = l, j = mid + 1;
for (int k = l; k <= r; k++) {
if (i > mid) { // 如果左半部分元素已经全部处理完毕
arr[k] = aux[j - l];
j++;
} else if (j > r) { // 如果右半部分元素已经全部处理完毕
arr[k] = aux[i - l];
i++;
} else if (aux[i - l] < aux[j - l]) { // 左半部分所指元素 < 右半部分所指元素
arr[k] = aux[i - l];
i++;
} else { // 左半部分所指元素 >= 右半部分所指元素
arr[k] = aux[j - l];
j++;
}
}
}
自底向上的归并排序
- 从左到右依次把数组分为小段，然后进行归并操作
- 没有使用数组直接访问索引的特性，可以对链表进行 O(nlogn) 排序
逆序对
- 一个数组抽取两个数字，如果有序，则为顺序对，否则为逆序对
- 衡量数组的有序程度
- 考察每一个数对。暴力解法算法复杂度：O(n^2)，使用归并排序达到 O(nlogn) 复杂度
快速排序（Quick Sort）
Partition
选出元素 V，arr[l+1...j]<V，[j+1...i-1]>V
优化
- Partition 递归操作递归到底时，在数据量较小时，可以选择插入排序。数据量越小，有序的可能性越大
- Partition 操作时随机选出元素 V（随机算法）。如果是有序或近乎有序的数组，Partition 操作选出的两个数组有可能退化为链表
- 有大量重复元素的数组，Partition 操作时把
=V的元素，尽量平均分配在<V和>V的部分
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
/**
* 快速排序
*
* @param arr
*/
public static void quickSort(int[] arr) {
int len = arr.length;
quickSort(arr, 0, len - 1);
}
// 递归使用快速排序,对 arr[l...r] 的范围进行排序
private static void quickSort(int[] arr, int l, int r) {
if (l >= r) {
return;
}
int p = partition(arr, l, r);
quickSort(arr, l, p - 1);
quickSort(arr, p + 1, r);
}
// 对 arr[l...r] 进行 partition 操作
// 返回 p, 使得 arr[l...p-1] < arr[p]; arr[p+1...r] > arr[p]
private static int partition(int[] arr, int l, int r) {
// 随机在 arr[l...r] 的范围中, 选择一个数值作为标定点 pivot
swap( arr, l , (int)(Math.random()*(r-l+1))+l );
int v = arr[l];
int j = l; // arr[l+1...j] < v ; arr[j+1...i) > v
for (int i = l + 1; i <= r; i++) {
if (arr[i] < v) {
j++;
swap(arr, j, i);
}
}
swap(arr, l, j);
return j;
}
三路快速排序（Quick Sort 3 Ways）
适合有大量重复元素的数组
应用
取出数组中第 n 大的元素
- 取出数组中的最大值、最大值。遍历，算法复杂度：O(n)
- 排序，算法复杂度：O(nlogn)
- 快速排序，算法复杂度：O(n)
堆排序（Heap Sort）
运用最大堆的特性，插入待排序数组的数据，然后取出数据 extractMax()
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
/**
* 堆排序
*
* @param arr
*/
public static void heapSort(int[] arr) {
int len = arr.length;
for (int i = (len - 1 - 1) / 2; i >= 0; i--) {
shiftDown(arr, len, i);
}
for (int i = len - 1; i > 0; i--) {
swap(arr, 0, i);
shiftDown(arr, i, 0);
}
}
private static void shiftDown(int[] arr, int len, int k) {
while (2 * k + 1 < len) {
int j = 2 * k + 1;
if (j + 1 < len && arr[j + 1] > arr[j]) {
j += 1;
}
if (arr[k] >= arr[j]) {
break;
}
swap(arr, k, j);
k = j;
}
}
原地堆排序
- heapify 操作，选出最大元素（数组首元素），与数组末尾元素交换
- 前半部分数组首元素
Shift Down操作，选出最大元素（数组首元素），与前半部分数组末尾元素交换 - 依次类推，直到前半部分数组个数为 1，排序完成
空间复杂度为 O(1)
多路归并排序
- 一般归并排序是分为两个数组，然后分别对两个数组中的两个元素进行比较
- 多路则把数组分为多个数组，然后对多个元素放入堆中进行比较
- 如果路数变为元素的个数，只需要递归一次即排序完成，此时退化为堆排序
- 多路归并排序是归并排序和堆排序的组合
排序算法的稳定性
- 稳定排序：对于相等的元素，在排序后，原来靠前的元素依然靠前，相等元素的相对位置没有发生改变
- 插入排序：「后面数组的元素 < 前面数组的元素」，则交换相等的元素，则会依次排列
- 归并排序：归并过程中，「后面数组的元素 < 前面数组的元素」，才会归并后面数组的元素，相等时前面数组的元素先归并
- 快速排序：在
Partition操作中，选出元素V时，可能破坏稳定性 - 堆排序：在
heapify过程中，可能破坏稳定性 - 可以通过自定义比较函数，让排序算法不存在稳定性的问题
算法复杂度分析中的符号
- Θ，读音：theta、西塔；既是上界也是下界(tight)，等于的意思。
- Ο，读音：big-oh、Omicron（欧米可荣，大写）；表示上界(tightness unknown)，小于等于的意思。
- ο，读音：small-oh、Omicron（欧米可荣，小写）；表示上界(not tight)，小于的意思。
- Ω，读音：big omega、欧米伽（大写）；表示下界(tightness unknown)，大于等于的意思。
- ω，读音：small omega、欧米伽（小写）；表示下界(not tight)，大于的意思。
排序算法的复杂度
| Algorithm | Time Complexity | Space Complexity | ||
|---|---|---|---|---|
| Best | Average | Worst | Worst | |
| Quicksort | Ω(n log(n)) |
Θ(n log(n)) |
O(n^2) |
O(log(n)) |
| Mergesort | Ω(n log(n)) |
Θ(n log(n)) |
O(n log(n)) |
O(n) |
| Timsort | Ω(n) |
Θ(n log(n)) |
O(n log(n)) |
O(n) |
| Heapsort | Ω(n log(n)) |
Θ(n log(n)) |
O(n log(n)) |
O(1) |
| Bubble Sort | Ω(n) |
Θ(n^2) |
O(n^2) |
O(1) |
| Insertion Sort | Ω(n) |
Θ(n^2) |
O(n^2) |
O(1) |
| Selection Sort | Ω(n^2) |
Θ(n^2) |
O(n^2) |
O(1) |
| Tree Sort | Ω(n log(n)) |
Θ(n log(n)) |
O(n^2) |
O(n) |
| Shell Sort | Ω(n log(n)) |
Θ(n(log(n))^2) |
O(n(log(n))^2) |
O(1) |
| Bucket Sort | Ω(n+k) |
Θ(n+k) |
O(n^2) |
O(n) |
| Radix Sort | Ω(nk) |
Θ(nk) |
O(nk) |
O(n+k) |
| Counting Sort | Ω(n+k) |
Θ(n+k) |
O(n+k) |
O(k) |
| Cubesort | Ω(n) |
Θ(n log(n)) |
O(n log(n)) |
O(n) |
算法设计
- 分治算法：分而治之，将原问题分割成同等结构的子问题，之后将子问题逐一解决后，原问题也得到了解决
- 分治：归并排序、快速排序、树结构
- 贪心：选择排序、堆、Kruskal、Prim、Dijkstra
- 递归回溯：树的遍历、图的遍历
- 动态规划：Prim、Dijkstra
