Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Appearance settings

Commit 91dab8d

Browse filesBrowse files
hicfhicf
committed
1.优化了基础排序算法代码；2.添加了二叉树遍历、二叉树深度、LRU缓存机制的代码
1 parent c171854 commit 91dab8d
Copy full SHA for 91dab8d

File tree

Expand file treeCollapse file tree

5 files changed

+436
-91
lines changed
Open diff view settings
Filter options
Expand file treeCollapse file tree

5 files changed

+436
-91
lines changed
Open diff view settings
Collapse file

‎README.md‎

Copy file name to clipboardExpand all lines: README.md
+3-1Lines changed: 3 additions & 1 deletion
  • Display the source diff
  • Display the rich diff
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:集合框架源码分析
Collapse file

‎resource/markdown/algorithm/BasicSorting.md‎

Copy file name to clipboardExpand all lines: resource/markdown/algorithm/BasicSorting.md
+104-47Lines changed: 104 additions & 47 deletions
  • Display the source diff
  • Display the rich diff
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++];
Collapse file

‎resource/markdown/algorithm/BinaryTreeDepth.md‎

Copy file name to clipboard
+89Lines changed: 89 additions & 0 deletions
  • Display the source diff
  • Display the rich diff
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 (0)
Morty Proxy This is a proxified and sanitized view of the page, visit original site.