添加了基础排序算法和二叉树的遍历 · codecodeabc/JavaCore@c171854 · GitHub
Skip to content

Commit c171854

Browse files
hicfhicf
committed
添加了基础排序算法和二叉树的遍历
1 parent 3b55156 commit c171854

3 files changed

Lines changed: 376 additions & 3 deletions

File tree

‎README.md‎

Lines changed: 11 additions & 3 deletions

‎resource/markdown/algorithm/BasicSorting.md‎

Lines changed: 245 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,245 @@
1+
### 常见基础排序算法
2+
3+
4+
5+
#### 排序算法分类
6+
7+
![排序算法分类](https://i.loli.net/2019/06/10/5cfe3bf15a32392750.png)
8+
9+
10+
#### 时间复杂度
11+
12+
| 排序算法 | 最好(时间复杂度) | 平均(时间复杂度) | 最坏(时间复杂度) | 稳定性 | 空间复杂度 |
13+
| ------------ | ------------------------- | ------------------------- | ------------------------- | ------ | -------------------------------- |
14+
| 冒泡排序 | **O**(n) | **O**(n<sup>2</sup>) | **O**(n<sup>2</sup>) | 稳定 | **O**(1) |
15+
| **快速排序** | **O**(n*log<sub>2</sub>n) | **O**(n*log<sub>2</sub>n) | **O**(n<sup>2</sup>) | 不稳定 | **O**(log<sub>2</sub>n)~**O**(n) |
16+
| 直接插入排序 | **O**(n) | **O**(n<sup>2</sup>) | **O**(n<sup>2</sup>) | 稳定 | **O**(1) |
17+
| **希尔排序** | **O**(n) | **O**(n<sup>1.3</sup>) | **O**(n<sup>2</sup>) | 不稳定 | **O**(1) |
18+
| 简单选择排序 | **O**(n) | **O**(n<sup>2</sup>) | **O**(n<sup>2</sup>) | 不稳定 | **O**(1) |
19+
| **堆排序** | **O**(n*log<sub>2</sub>n) | **O**(n*log<sub>2</sub>n) | **O**(n*log<sub>2</sub>n) | 不稳定 | **O**(1) |
20+
| **归并排序** | **O**(n*log<sub>2</sub>n) | **O**(n*log<sub>2</sub>n) | **O**(n*log<sub>2</sub>n) | 稳定 | **O**(n) |
21+
| 基数排序 | **O**(d*(r+n)) | **O**(d*(r+n)) | **O**(d*(r+n)) | 稳定 | **O**(r*d+n) |
22+
23+
24+
25+
#### 各种复杂度效率比较图
26+
27+
```java
28+
O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(2^n) < O(n^3) < O(n^n)
29+
```
30+
31+
![各种时间复杂度效率比较图](https://i.loli.net/2019/06/11/5cff235ba9b9a93703.jpg)
32+
33+
**说明：** n 越大，越能体现算法效率。当 n 比较小时，复杂度会有一波小交叉，上图不考虑 n 比较小的情况。
34+
35+
36+
37+
##### 1. 冒泡排序 ★☆☆☆☆
38+
39+
```java
40+
public void bubbleSort(int[] array) {
41+
int temp;
42+
// 外层移动基准元素索引
43+
for (int i = 0; i < array.length - 1; i++) {
44+
// 内层对基准元素与之后的每个做比较，冒泡排序
45+
for (int j = i + 1; j < array.length; j++) {
46+
// 大的值，向上冒泡
47+
if ((temp = array[i]) > array[j]) {
48+
array[i] = array[j];
49+
array[j] = temp;
50+
}
51+
}
52+
}
53+
}
54+
```
55+
56+
57+
58+
##### 2. 快速排序 ★★★★★
59+
60+
```java
61+
public void quickSort(int[] array, int left, int right) {
62+
if (left < right) {
63+
int i = left;
64+
int j = right;
65+
int temp = array[i];
66+
67+
while (i < j) {
68+
while (i < j && array[j] >= temp) {
69+
j--;
70+
}
71+
if (i < j) {
72+
array[i++] = array[j];
73+
}
74+
75+
while (i < j && array[i] <= temp) {
76+
i++;
77+
}
78+
if (i < j) {
79+
array[j--] = array[i];
80+
}
81+
82+
array[i] = temp;
83+
quickSort(array, left, i - 1);
84+
quickSort(array, i + 1, right);
85+
}
86+
}
87+
}
88+
```
89+
90+
91+
92+
##### 3. 直接插入排序 ★★★☆☆
93+
94+
```java
95+
public void insertionSort(int[] array) {
96+
for (int i = 0; i < array.length; i++) {
97+
int temp = array[i];
98+
int j;
99+
for (j = i; j > 0 && array[j - 1] > temp; j--) {
100+
array[j] = array[j - 1];
101+
}
102+
if (array[j] > temp) {
103+
array[j] = temp;
104+
}
105+
}
106+
}
107+
```
108+
109+
110+
111+
##### 4. 希尔排序 ★★★☆☆
112+
113+
```java
114+
public void shellSort(int[] array) {
115+
// 增量
116+
for (int d = array.length / 2; d > 0; d /= 2) {
117+
// 分组
118+
for (int x = 0; x < d; x++) {
119+
// 直接插入排序(第 x 组的第2个元素起步)
120+
for (int i = x + d; i < array.length; i += d) {
121+
int temp = array[i];
122+
int j = i;
123+
for (; j > d && array[j - d] > temp; j -= d) {
124+
array[j] = array[j - d];
125+
}
126+
if (array[j] > temp) {
127+
array[j] = temp;
128+
}
129+
}
130+
}
131+
}
132+
}
133+
```
134+
135+
136+
137+
##### 5. 简单选择排序 ★★☆☆☆
138+
139+
```java
140+
public void selectionSort(int[] array) {
141+
int minIndex;
142+
int temp;
143+
for (int i = 0; i < array.length - 1; i++) {
144+
minIndex = i;
145+
for (int j = i + 1; j < array.length; j ++) {
146+
if (array[minIndex] > array[j]) {
147+
minIndex = j;
148+
}
149+
}
150+
if (minIndex > i) {
151+
temp = array[i];
152+
array[i] = array[minIndex];
153+
array[minIndex] = temp;
154+
}
155+
}
156+
}
157+
```
158+
159+
160+
161+
##### 6. 堆排序 ★★★★☆
162+
163+
```java
164+
public void heapSort(int[] array) {
165+
for (int i = array.length / 2 - 1; i >= 0; i--) {
166+
adjustHeap(array, i, array.length);
167+
}
168+
169+
for (int i = array.length - 1; i > 0; i--) {
170+
swap(array, 0, i);
171+
adjustHeap(array, 0, i);
172+
}
173+
}
174+
175+
private void adjustHeap(int[] array, int i, int length) {
176+
int temp = array[i];
177+
178+
for (int j = i * 2 + 1; j < length; j = j * 2 + 1) {
179+
if (j + 1 < length && array[j + 1] > array[j]) {
180+
j++;
181+
}
182+
if (array[j] > temp) {
183+
array[i] = array[j];
184+
i = j;
185+
} else {
186+
break;
187+
}
188+
}
189+
array[i] = temp;
190+
}
191+
192+
private void swap(int[] array, int a, int b) {
193+
int temp = array[a];
194+
array[a] = array[b];
195+
array[b] = temp;
196+
}
197+
```
198+
199+
200+
201+
##### 7. 归并排序 ★★★★☆
202+
203+
```java
204+
public void mergeSort(int[] array) {
205+
int[] aux = new int[array.length];
206+
sort(array, 0, array.length - 1, aux);
207+
}
208+
209+
private void sort(int[] array, int left, int right,int[] aux) {
210+
if (left < right) {
211+
int mid = (left + right) / 2;
212+
sort(array, left , mid, aux);
213+
sort(array, mid + 1, right, aux);
214+
merge(array, left, mid, right, aux);
215+
}
216+
}
217+
218+
private void merge(int[] array, int left, int mid, int right, int[] aux){
219+
int l = left;
220+
int m = mid + 1;
221+
int t = 0;
222+
223+
while (l <= mid && m <= right) {
224+
if (array[l] <= array[m]) {
225+
aux[t++] = array[l++];
226+
} else {
227+
aux[t++] = array[m++];
228+
}
229+
}
230+
231+
// 填充剩余元素
232+
while (l <= mid) {
233+
aux[t++] = array[l++];
234+
}
235+
while (m <= right) {
236+
aux[t++] = array[m++];
237+
}
238+
239+
t = 0;
240+
while (left <= right) {
241+
array[left++] = aux[t++];
242+
}
243+
}
244+
```
245+

‎resource/markdown/algorithm/BinaryTreeTraversal.md‎

Lines changed: 120 additions & 0 deletions

0 commit comments

Comments
 (0)