Skip to content

Commit a35b670

Browse files
author
代码风水师
authored
Merge pull request hicf#3 from about-cloud/dev
1.优化了基础排序算法代码；2.添加了二叉树遍历、二叉树深度、LRU缓存机制的代码
2 parents c171854 + 91dab8d commit a35b670

File tree

5 files changed

+436
-91
lines changed

5 files changed

+436
-91
lines changed

‎README.md

Lines changed: 3 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -8,8 +8,10 @@
88

99
### 零、:rocket::rocket::rocket:数据结构与算法
1010

11-
* [数据结构与算法 （第 01 篇） Java版：常见基础排序算法与复杂度](https://github.com/about-cloud/JavaCore/blob/master/resource/markdown/algorithm/BasicSorting.md)
11+
* [数据结构与算法 （第 01 篇） Java版：常见基础排序算法及复杂度](https://github.com/about-cloud/JavaCore/blob/master/resource/markdown/algorithm/BasicSorting.md)
1212
* [数据结构与算法 （第 02 篇） Java版：二叉树遍历的n种方法](https://github.com/about-cloud/JavaCore/blob/master/resource/markdown/algorithm/BinaryTreeTraversal.md)
13+
* [数据结构与算法 （第 03 篇） Java版：二叉树深度](https://github.com/about-cloud/JavaCore/blob/master/resource/markdown/algorithm/BinaryTreeDepth.md)
14+
* [数据结构与算法 （第 04 篇） Java版：LRU缓存机制](https://github.com/about-cloud/JavaCore/blob/master/resource/markdown/algorithm/LRUCache.md)
1315

1416

1517
### 一、:bullettrain_side::railway_car::railway_car::railway_car:集合框架源码分析

‎resource/markdown/algorithm/BasicSorting.md

Lines changed: 104 additions & 47 deletions
Original file line numberDiff line numberDiff line change
@@ -1,10 +1,10 @@
1-
### 常见基础排序算法
1+
### 2常见基础排序算法
22

33

44

55
#### 排序算法分类
66

7-
![排序算法分类](https://i.loli.net/2019/06/10/5cfe3bf15a32392750.png)
7+
![排序算法分类](http://ww2.sinaimg.cn/large/006y8mN6ly1g68uopou69j30ko0dzwgb.jpg)
88

99

1010
#### 时间复杂度
@@ -38,51 +38,73 @@ O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(2^n) < O(n^3) < O(n^n)
3838

3939
```java
4040
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-
}
41+
if (array == null) {
42+
return;
43+
}
44+
45+
int temp;
46+
// 冒泡次数
47+
for (int i = array.length - 1; i > 0; i--) {
48+
// 冒泡排序
49+
for (int j = 0; j < i; j++) {
50+
// 将大值交换到后面
51+
if (array[j] > array[j + 1]) {
52+
temp = array[j];
53+
array[j] = array[j + 1];
54+
array[j + 1] = temp;
55+
}
56+
}
57+
}
5358
}
5459
```
5560

5661

5762

5863
##### 2. 快速排序 ★★★★★
5964

65+
基本思想：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
66+
6067
```java
6168
public void quickSort(int[] array, int left, int right) {
69+
if (array == null) {
70+
return;
71+
}
72+
6273
if (left < right) {
6374
int i = left;
6475
int j = right;
65-
int temp = array[i];
76+
int temp = array[i]; // 选取一端值为基准值
6677

6778
while (i < j) {
79+
// 如果 j 处值大于等于基准值，那么不用交换数据，直接将 j 向前移动，
80+
// 直到 i 等于 j 或者 j 处值比基准值小
6881
while (i < j && array[j] >= temp) {
6982
j--;
7083
}
84+
// 如果 i < j，说明 j 处值比基准值小(根据上面循环判断)
7185
if (i < j) {
86+
// 交换 j 与 i 处的值，并将 i 向后移动
7287
array[i++] = array[j];
7388
}
7489

90+
91+
// 如果 i 处值小于等于基准值，那么将i向后移动就可以了
7592
while (i < j && array[i] <= temp) {
7693
i++;
7794
}
95+
// 如果 i < j，说明 i 处值比基准值大(根据上面循环判断)
7896
if (i < j) {
97+
// 交换 i 与 j 处的值，并将 i 向前移动
7998
array[j--] = array[i];
8099
}
81100

101+
// 最后将临时基准值填充到 i 处
82102
array[i] = temp;
83-
quickSort(array, left, i - 1);
84-
quickSort(array, i + 1, right);
103+
// 对两段各自快速排序
85104
}
105+
106+
quickSort(array, left, i - 1);
107+
quickSort(array, i + 1, right);
86108
}
87109
}
88110
```
@@ -93,12 +115,18 @@ public void quickSort(int[] array, int left, int right) {
93115

94116
```java
95117
public void insertionSort(int[] array) {
118+
if (array == null) {
119+
return;
120+
}
121+
// 和冒泡排序有些类似，这里是遍历趟数
96122
for (int i = 0; i < array.length; i++) {
97-
int temp = array[i];
123+
// 精髓是从局部有序，到整体有序
124+
int temp = array[i]; // 当前基准元素
98125
int j;
99126
for (j = i; j > 0 && array[j - 1] > temp; j--) {
100-
array[j] = array[j - 1];
127+
array[j] = array[j - 1]; // 下一个元素比基准元素大，下一个元素向后移动
101128
}
129+
// 最后比较当前元素和基准元素大小
102130
if (array[j] > temp) {
103131
array[j] = temp;
104132
}
@@ -108,19 +136,22 @@ public void insertionSort(int[] array) {
108136

109137

110138

111-
##### 4. 希尔排序 ★★★☆☆
139+
##### 4. 希尔排序（缩写增量-直接插入排序） ★★★☆☆
112140

113141
```java
114142
public void shellSort(int[] array) {
115-
// 增量
143+
if (array == null) {
144+
return;
145+
}
146+
// 计算增量
116147
for (int d = array.length / 2; d > 0; d /= 2) {
117148
// 分组
118-
for (int x = 0; x < d; x++) {
119-
// 直接插入排序(第 x 组的第2个元素起步)
120-
for (int i = x + d; i < array.length; i += d) {
149+
for (int g = 0; g < d; g++) {
150+
// 插入排序(第 x 组的第 d 个增量元素起步)(直接插入排序的增量是 1，这里是 d，需注意下)
151+
for (int i = g + d; i < array.length; i += d) {
121152
int temp = array[i];
122-
int j = i;
123-
for (; j > d && array[j - d] > temp; j -= d) {
153+
int j;
154+
for (j = i; j > d && array[j - d] > temp; j -= d) {
124155
array[j] = array[j - d];
125156
}
126157
if (array[j] > temp) {
@@ -138,19 +169,26 @@ public void shellSort(int[] array) {
138169

139170
```java
140171
public void selectionSort(int[] array) {
141-
int minIndex;
172+
if (array == null) {
173+
return;
174+
}
175+
176+
int index;
142177
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;
178+
// 做出的选择次数
179+
for (int i = array.length - 1; i > 0; i--) {
180+
index = 0;
181+
for (int j = 1; j < i; j++) {
182+
// 选择一个最大的值(记录索引)
183+
if (array[j] > array[index]) {
184+
index = j;
148185
}
149186
}
150-
if (minIndex > i) {
151-
temp = array[i];
152-
array[i] = array[minIndex];
153-
array[minIndex] = temp;
187+
// 将选出的最大值换到一端
188+
if (array[index] > array[i]) {
189+
temp = array[index];
190+
array[index] = array[i];
191+
array[i] = temp;
154192
}
155193
}
156194
}
@@ -162,31 +200,43 @@ public void selectionSort(int[] array) {
162200

163201
```java
164202
public void heapSort(int[] array) {
203+
if (array == null) {
204+
return;
205+
}
206+
165207
for (int i = array.length / 2 - 1; i >= 0; i--) {
208+
// 先调整堆(选择一个最大值放到堆顶)
166209
adjustHeap(array, i, array.length);
167210
}
168211

169212
for (int i = array.length - 1; i > 0; i--) {
213+
// 将堆顶的元素与其他元素比较并交换
170214
swap(array, 0, i);
215+
// 再调整堆
171216
adjustHeap(array, 0, i);
172217
}
173218
}
174219

175-
private void adjustHeap(int[] array, int i, int length) {
176-
int temp = array[i];
220+
// 调整堆，使得堆顶元素值大于等于其子节点值
221+
private void adjustHeap(int[] array, int top, int length) {
222+
int temp = array[top];
177223

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++;
224+
for (int i = top * 2 + 1; i < length; i = i * 2 + 1) {
225+
// （如果存在的化）从左右子节点找出值最大的子节点
226+
if (i + 1 < length && array[i + 1] > array[i]) {
227+
i++;
181228
}
182-
if (array[j] > temp) {
183-
array[i] = array[j];
184-
i = j;
229+
if (array[i] > temp) {
230+
array[top] = array[i];
231+
top = i;
185232
} else {
186233
break;
187234
}
188235
}
189-
array[i] = temp;
236+
237+
if (array[top] > temp) {
238+
array[top] = temp;
239+
}
190240
}
191241

192242
private void swap(int[] array, int a, int b) {
@@ -202,24 +252,30 @@ private void swap(int[] array, int a, int b) {
202252

203253
```java
204254
public void mergeSort(int[] array) {
255+
if (array == null) {
256+
return;
257+
}
258+
205259
int[] aux = new int[array.length];
206260
sort(array, 0, array.length - 1, aux);
207261
}
208262

209263
private void sort(int[] array, int left, int right,int[] aux) {
210264
if (left < right) {
211265
int mid = (left + right) / 2;
266+
// 先分后合
212267
sort(array, left , mid, aux);
213268
sort(array, mid + 1, right, aux);
214269
merge(array, left, mid, right, aux);
215270
}
216271
}
217272

218273
private void merge(int[] array, int left, int mid, int right, int[] aux){
274+
int t = 0;
219275
int l = left;
220276
int m = mid + 1;
221-
int t = 0;
222277

278+
// 判断元素值大小，按大小排序到辅助数组上
223279
while (l <= mid && m <= right) {
224280
if (array[l] <= array[m]) {
225281
aux[t++] = array[l++];
@@ -228,14 +284,15 @@ private void merge(int[] array, int left, int mid, int right, int[] aux){
228284
}
229285
}
230286

231-
// 填充剩余元素
287+
// 把剩余元素填充到辅助数组上
232288
while (l <= mid) {
233289
aux[t++] = array[l++];
234290
}
235291
while (m <= right) {
236292
aux[t++] = array[m++];
237293
}
238294

295+
// 将辅助线数组上的元素复制到需要排序的数组上
239296
t = 0;
240297
while (left <= right) {
241298
array[left++] = aux[t++];

‎resource/markdown/algorithm/BinaryTreeDepth.md

Lines changed: 89 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,89 @@
1+
### 二叉树的最小深度
2+
3+
4+
5+
> 给定一个二叉树，找出其最小深度。
6+
>
7+
> 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
8+
9+
**说明:** 叶子节点是指没有子节点的节点。
10+
11+
12+
13+
##### 0. 定义一个二叉树节点
14+
15+
```java
16+
public class TreeNode {
17+
int val;
18+
TreeNode left;
19+
TreeNode right;
20+
TreeNode(int x) {
21+
val = x;
22+
}
23+
}
24+
```
25+
26+
27+
28+
##### 1. 递归
29+
30+
```java
31+
public class Solution {
32+
public int minDepth(TreeNode root) {
33+
if (root == null) {
34+
return 0;
35+
}
36+
37+
// 递归计算
38+
int leftMinDepth = minDepth(root.left);
39+
int rightMinDepth = minDepth(root.right);
40+
41+
// 有子节点为空的，则返回另一个节点的深度。否则返回两则最小的深度。
42+
return leftMinDepth == 0 || rightMinDepth == 0
43+
? leftMinDepth + rightMinDepth + 1
44+
: Math.min(leftMinDepth, rightMinDepth) + 1;
45+
}
46+
}
47+
```
48+
49+
50+
51+
##### 2. 非递归（宽度优先搜索）
52+
53+
> 出现第一个无子节点的节点，则该节点的深度为树的最小深度
54+
55+
```java
56+
public class Solution {
57+
public int minDepth(TreeNode root) {
58+
if (root == null) {
59+
return 0;
60+
}
61+
62+
Queue<TreeNode> queue = new LinkedList<>();
63+
queue.offer(root);
64+
65+
int minDepth = 0;
66+
while (!queue.isEmpty()) {
67+
++minDepth;
68+
69+
// 逐层遍历，判断一层是否存在没有子节点的节点，则该节点的深度为树的最小深度
70+
int size = queue.size();
71+
for (int i = 0; i < size; i++) {
72+
root = queue.poll();
73+
if (root.left == null && root.right == null) {
74+
return minDepth;
75+
}
76+
if (root.left != null) {
77+
queue.offer(root.left);
78+
}
79+
if (root.right != null) {
80+
queue.offer(root.right);
81+
}
82+
}
83+
}
84+
85+
return minDepth;
86+
}
87+
}
88+
```
89+

0 commit comments

Comments
 (0)