Skip to content

Commit 1d0a76f

Browse files
coderbruiscoderbruis
committed
添加堆排序以及排序git动态图
1 parent 778e336 commit 1d0a76f

8 files changed

Lines changed: 244 additions & 4 deletions

File tree

‎notes/algorithms/基础排序算法.md‎

Lines changed: 14 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -21,7 +21,9 @@
2121

2222
#### 1. 冒泡排序
2323

24-
> 思路：每一趟遍历将最大元素冒泡到数组最后的位置；
24+
思路：每一趟遍历将最大元素冒泡到数组最后的位置；
25+
26+
![冒泡排序动态图](https://github.com/coderbruis/AlgorithmsInJava/blob/master/notes/pictures/bubbleSort.gif)
2527

2628
```
2729
public class BubbleSort {
@@ -105,6 +107,8 @@ public class BubbleSort {
105107

106108
思路：依次寻找[i, n)区间里的最小值的索引。
107109

110+
![选择排序动态图](https://github.com/coderbruis/AlgorithmsInJava/blob/master/notes/pictures/selectionSort.gif)
111+
108112
```
109113
public class SelectionSort {
110114
@@ -135,6 +139,8 @@ public class SelectionSort {
135139

136140
思路：插入排序就跟玩扑克牌一样，先把一部分牌给排好顺序，然后依次往后排剩下的牌，最终达到将所有牌都排序的效果。
137141

142+
![插入排序动态图](https://github.com/coderbruis/AlgorithmsInJava/blob/master/notes/pictures/insertionSort.gif)
143+
138144
```
139145
public class InsertionSort {
140146
// 方式1
@@ -337,17 +343,21 @@ public void sort(int[] nums) {
337343

338344
#### 8. 桶排序
339345

346+
#### 9. 堆排序
347+
348+
- [堆排序详细分析]()
349+
340350
#### 排序总结
341351

342-
| 排序名 | 时间复杂度 | 空间复杂度 | 优势 | 劣势 | 适用场景 | 稳定性 |
352+
| 排序名 | 平均时间复杂度 | 空间复杂度 | 优势 | 劣势 | 适用场景 | 稳定性 |
343353
| :--: | :------: | :----------: | :--: | :--: | :-----------------------: | :--: |
344354
| 冒泡排序 | O(n^2) | O(1) | | | | 稳定 |
345355
| 插入排序 | O(n^2) | O(1) | | | | 稳定 |
346-
| 归并排序 | O(nlogn) | O(N) | | | | 稳定 |
347356
| 计数排序 | | O(M) | | | 对于用例少的数据，比如对人的年龄排序或者身高排序。 | 稳定 |
348-
| 基数排序 | | O(M) | | | | 稳定 |
357+
| 基数排序 | O(d(n+r)) | O(M) | | | | 稳定 |
349358
| 桶排序 | | | | | | 稳定 |
350359
| 选择排序 | O(n^2) | O(1) | | | | 不稳定 |
360+
| 归并排序 | O(nlogn) | O(N) | | | | 稳定 |
351361
| 快速排序 | O(nlogn) | O(logn)~O(n) | | | | 不稳定 |
352362
| 希尔排序 | O(nlogn) | O(1) | | | | 不稳定 |
353363
| 堆排序 | O(nlogn) | O(1) | | | | 不稳定 |

‎notes/pictures/bubbleSort.gif‎

343 KB
Loading

‎notes/pictures/insertionSort.gif‎

360 KB
Loading

‎notes/pictures/selectionSort.gif‎

459 KB
Loading

‎src/main/java/com/bruis/algorithminjava/algorithm/sort/BubbleSort.java‎

Lines changed: 78 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,78 @@
1+
package com.bruis.algorithminjava.algorithm.sort;
2+
3+
/**
4+
* @author LuoHaiYang
5+
*/
6+
public class BubbleSort {
7+
8+
// 方式1
9+
public static void sort(int[] arr) {
10+
int n = arr.length;
11+
boolean swapped = false;
12+
13+
do {
14+
swapped = false;
15+
for (int i = 1; i < n; i++) {
16+
if (arr[i - 1] > arr[i]) {
17+
swap(arr, i - 1, i);
18+
swapped = true;
19+
}
20+
}
21+
} while(swapped);
22+
}
23+
24+
// 方式2
25+
public static void sort2(int[] arr) {
26+
int n = arr.length;
27+
28+
if (n <= 1) {
29+
return;
30+
}
31+
32+
// 使用newn来进行优化
33+
int newn;
34+
35+
do {
36+
newn = 0;
37+
for (int i = 1; i < n; i++) {
38+
if (arr[i - 1] > arr[i]) {
39+
swap(arr, i - 1, i);
40+
// 记录当前排序最后一次交换的位置，在此之后的元素在下一轮扫描中均不考虑
41+
newn = i;
42+
}
43+
}
44+
n = newn;
45+
} while (newn > 0);
46+
47+
}
48+
49+
// 方式3
50+
public static void sort3(int[] arr) {
51+
int n = arr.length;
52+
if (n <= 1) {
53+
return;
54+
}
55+
56+
for (int i = 0; i < n; i++) {
57+
boolean flag = false;
58+
59+
// n - i - 1 表示每轮排序都会有一个最大元素冒泡到最大位置，因而每轮排序都会少一个遍历的元素
60+
for (int j = 0; j < n - i - 1; j++) {
61+
if (arr[j] < arr[j + 1]) {
62+
swap(arr, j, j + 1);
63+
flag = true;
64+
}
65+
}
66+
// 此轮排序没有数据交换，则退出排序
67+
if (!flag) {
68+
break;
69+
}
70+
}
71+
}
72+
73+
public static void swap(int[] arr, int i, int j) {
74+
int tmp = arr[i];
75+
arr[i] = arr[j];
76+
arr[j] = tmp;
77+
}
78+
}

‎src/main/java/com/bruis/algorithminjava/algorithm/sort/HeapSort.java‎

Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
package com.bruis.algorithminjava.algorithm.sort;
2+
3+
/**
4+
* @author LuoHaiYang
5+
*/
6+
public class HeapSort {
7+
8+
public static void sort(int[] arr) {
9+
int n = arr.length;
10+
11+
// 注意，此时我们的堆是从0开始索引的
12+
// 从(最后一个元素的索引-1)/2开始
13+
// 最后一个元素的索引 = n-1
14+
for (int i = (n - 1 - 1) / 2; i >= 0; i--) {
15+
shiftDown(arr, n, i);
16+
}
17+
}
18+
19+
// 下浮
20+
public static void shiftDown(int[] arr, int n, int k) {
21+
22+
while (2 * k + 1 < n) {
23+
int j = 2 * k + 1;
24+
if (j + 1 < n && arr[j+1] > arr[j]) {
25+
j += 1;
26+
}
27+
if (arr[k] >= arr[j]) {
28+
break;
29+
}
30+
swap(arr, k, j);
31+
k = j;
32+
}
33+
}
34+
35+
public static void swap(int[] arr, int i, int j) {
36+
int tmp = arr[i];
37+
arr[i] = arr[j];
38+
arr[j] = tmp;
39+
}
40+
}

‎src/main/java/com/bruis/algorithminjava/algorithm/sort/MergeSortAdvanced01.java‎

Lines changed: 57 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,57 @@
1+
package com.bruis.algorithminjava.algorithm.sort;
2+
3+
import java.util.Arrays;
4+
5+
/**
6+
*
7+
* 归并排序优化版本1
8+
*
9+
* @author LuoHaiYang
10+
*/
11+
public class MergeSortAdvanced01 {
12+
13+
public static void merge(int[] arr, int left, int mid, int right) {
14+
15+
int[] aux = Arrays.copyOfRange(arr, left, right + 1);
16+
17+
int i = left, j = mid + 1;
18+
for (int k = left; k <= right; k++) {
19+
if (i > mid) {
20+
arr[k] = aux[j-left];
21+
j++;
22+
} else if (j > right) {
23+
arr[k] = aux[i-left];
24+
i++;
25+
} else if (aux[i-left] < aux[j-left]) {
26+
arr[k] = aux[i-left];
27+
i++;
28+
} else {
29+
arr[k] = aux[j-left];
30+
j++;
31+
}
32+
}
33+
}
34+
35+
public static void sort(int[] arr, int left, int right) {
36+
37+
// 优化2: 对于小规模数组, 使用插入排序
38+
if (right - left <= 15) {
39+
InsertionSort.sort(arr);
40+
return;
41+
}
42+
43+
int mid = (left + right) / 2;
44+
sort(arr, left, mid);
45+
sort(arr, mid + 1, right);
46+
47+
// 优化1: 对于arr[mid] <= arr[mid+1]的情况,不进行merge
48+
// 对于近乎有序的数组非常有效,但是对于一般情况,有一定的性能损失
49+
if (arr[mid] > arr[mid+1]) {
50+
merge(arr, left, mid, right);
51+
}
52+
}
53+
public static void sort(int[] arr) {
54+
int n = arr.length;
55+
sort(arr, 0, n-1);
56+
}
57+
}

‎src/main/java/com/bruis/algorithminjava/algorithm/sort/QuickSort.java‎

Lines changed: 55 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,55 @@
1+
package com.bruis.algorithminjava.algorithm.sort;
2+
3+
/**
4+
*
5+
* 快速排序
6+
*
7+
* @author LuoHaiYang
8+
*/
9+
public class QuickSort {
10+
11+
/**
12+
* 对arr[left...right]部分进行partition操作
13+
* 返回p, 使得arr[left...p-1] < arr[p] ; arr[p+1...right] > arr[p]
14+
*
15+
* @param arr
16+
* @param left
17+
* @param right
18+
* @return
19+
*/
20+
private static int partition(int[] arr, int left, int right) {
21+
22+
int p = arr[left];
23+
24+
// arr[left+1...j] < p; arr[j+1...i) > p
25+
int j = left;
26+
for (int i = left + 1; i <= right; i++) {
27+
if (arr[i] < p) {
28+
j++;
29+
swap(arr, j, i);
30+
}
31+
swap(arr, left, j);
32+
}
33+
return j;
34+
}
35+
36+
private static void sort(int[] arr, int left, int right) {
37+
if (left >= right) {
38+
return;
39+
}
40+
int p = partition(arr, left, right);
41+
sort(arr, left, p-1);
42+
sort(arr, p+1, right);
43+
}
44+
45+
public static void sort(int[] arr) {
46+
int n = arr.length;
47+
sort(arr, 0, n-1);
48+
}
49+
50+
private static void swap(int[] arr, int i, int j) {
51+
int tmp = arr[i];
52+
arr[i] = arr[j];
53+
arr[j] = tmp;
54+
}
55+
}

0 commit comments

Comments
 (0)