Skip to content

Commit 11a2cb9

Browse files
mercyblitzmercyblitz
committed
Add Stage 2 Lesson 4
1 parent d473e19 commit 11a2cb9

File tree

8 files changed

+322
-0
lines changed

8 files changed

+322
-0
lines changed

‎「一入 Java 深似海 」/代码/segmentfault/deep-in-java/stage-2/lesson-4/pom.xml

Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,15 @@
1+
<?xml version="1.0" encoding="UTF-8"?>
2+
<project xmlns="http://maven.apache.org/POM/4.0.0"
3+
xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
4+
xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
5+
<parent>
6+
<artifactId>stage-2</artifactId>
7+
<groupId>com.segmentfault</groupId>
8+
<version>1.0-SNAPSHOT</version>
9+
</parent>
10+
<modelVersion>4.0.0</modelVersion>
11+
12+
<artifactId>stage-2-lesson-4</artifactId>
13+
14+
15+
</project>

‎「一入 Java 深似海 」/代码/segmentfault/deep-in-java/stage-2/lesson-4/src/main/java/com/segmentfault/deep/in/java/collection/algorithm/BubbleSort.java

Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
1+
package com.segmentfault.deep.in.java.collection.algorithm;
2+
3+
import java.util.stream.Stream;
4+
5+
public class BubbleSort<T extends Comparable<T>> implements Sort<T> {
6+
7+
@Override
8+
public void sort(T[] values) {
9+
10+
// Comparable.compareTo
11+
// < return -1
12+
// = return 0
13+
// > return 1
14+
int size = values.length;
15+
16+
// Given array : [3,1,2,5,4]
17+
// for 1 |
18+
// for 2 |
19+
for (int i = 0; i < size; i++) {
20+
// 第 i 号元素
21+
T t = values[i]; // 产生临时变量
22+
for (int j = i + 1; j < size; j++) {
23+
// 第 i 号元素与 i + 1 对比
24+
if (t.compareTo(values[j]) == 1) { // 低位 > 高位
25+
// 交换元素 [i + 1] = [i]
26+
values[i] = values[j];
27+
values[j] = t;
28+
// [0] = 3 , [1] = 2
29+
// [1] = [1](2) + [0](3) = 5
30+
// [0] = [1](5) - [0](3) = 2
31+
// [1] = [1](5) - [0](2) = 3
32+
break;
33+
}
34+
}
35+
}
36+
}
37+
38+
public static void main(String[] args) {
39+
Integer[] values = Sort.of(3, 1, 2, 5, 4);
40+
Sort<Integer> sort = new BubbleSort<>(); // Java 7 Diamond 语法
41+
sort.sort(values);
42+
Stream.of(values).forEach(System.out::println);
43+
}
44+
45+
}

‎「一入 Java 深似海 」/代码/segmentfault/deep-in-java/stage-2/lesson-4/src/main/java/com/segmentfault/deep/in/java/collection/algorithm/InsertionSort.java

Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
package com.segmentfault.deep.in.java.collection.algorithm;
2+
3+
import java.util.stream.Stream;
4+
5+
public class InsertionSort<T extends Comparable<T>> implements Sort<T> {
6+
7+
@Override
8+
public void sort(T[] values) {
9+
// Comparable.compareTo
10+
// < return -1
11+
// = return 0
12+
// > return 1
13+
int size = values.length;
14+
for (int i = 1; i < size; i++) {
15+
// 高位数 t
16+
// [3, 1, 2, 5, 4]
17+
// [j = 0] = 3, [i = 1] = 1 , t = [i = 1] = 1
18+
// [i = 1] = [j = 0] , [j = 0] = t = 1
19+
T t = values[i]; // 产生临时变量
20+
for (int j = i - 1; j >= 0; j--) {
21+
if (t.compareTo(values[j]) < 1) { // 高位 < 低位
22+
values[i] = values[j]; // 高位获取低位的值
23+
values[j] = t; // 低位得到高位的值
24+
}
25+
}
26+
}
27+
}
28+
29+
public static void main(String[] args) {
30+
Integer[] values = Sort.of(3, 1, 2, 5, 4);
31+
Sort<Integer> sort = new InsertionSort<>(); // Java 7 Diamond 语法
32+
sort.sort(values);
33+
Stream.of(values).forEach(System.out::println);
34+
}
35+
36+
}

‎「一入 Java 深似海 」/代码/segmentfault/deep-in-java/stage-2/lesson-4/src/main/java/com/segmentfault/deep/in/java/collection/algorithm/MergeSort.java

Lines changed: 119 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,119 @@
1+
package com.segmentfault.deep.in.java.collection.algorithm;
2+
3+
import java.util.stream.Stream;
4+
5+
public class MergeSort<T extends Comparable<T>> implements Sort<T> {
6+
7+
8+
@Override
9+
public void sort(T[] values) {
10+
sort(values, 0, values.length - 1);
11+
}
12+
13+
private void merge(Comparable[] values, int low, int mid, int high) {
14+
15+
// 找到子数组进行合并
16+
// [3, 1, 2, 5, 4] , n = 5
17+
// low = 0
18+
// high = 4
19+
// mid = 2
20+
// a1 = [0...mid] = [3, 1, 2] = mid(2) - low(0) + 1 = 3个元素
21+
// a2 = [mid+1..high] = [3...4] = [5, 4] = high(4) - mid(2) = 2个元素
22+
int n1 = mid - low + 1;
23+
int n2 = high - mid;
24+
// 非 In-Place 实现(创建新的数组)
25+
Comparable[] a1 = new Comparable[n1];
26+
Comparable[] a2 = new Comparable[n2];
27+
28+
//把 values[0...mid] 内容复制给 a1
29+
System.arraycopy(values, 0, a1, 0, n1);
30+
//把 values[mid+1...high] 内容复制给 a2
31+
System.arraycopy(values, mid + 1, a2, 0, n2);
32+
33+
// i 为 n1 做迭代
34+
// j 为 n2 做迭代
35+
// 合并
36+
// [3, 1, 2, 5, 4]
37+
// a1 = [0...mid] = [3, 1, 2] = mid(2) - low(0) + 1 = 3个元素
38+
// a2 = [mid+1..high] = [3...4] = [5, 4] = high(4) - mid(2) = 2个元素
39+
// k = low(0)
40+
// a1[i=0](values[0]) = 3 compare a2[j=0](values[3]) = 5
41+
// values[k=0] = a1[i=0] = 3
42+
// i++;j++;k++;
43+
44+
// [3, 1(a1), 2, 5, 4(a2)]
45+
// a1[i=1](values[1]) = 1 compare a2[j=1](values[4]) = 4
46+
// values[k=1] = a1[1] = 1
47+
// i++;j++;k++;
48+
49+
// a1[i=2](values[2]) = 2
50+
// values[k=2] = 2
51+
52+
// [3, 1, 2]
53+
// mid = 2
54+
// a1 = [0...2] = [3, 1] = 2个元素
55+
// a2 = [2] = 2 = 1个元素
56+
57+
// a1[i=0](values[0]) = 3 compare a2[j=0](values[2]) = 2
58+
// values[k=0] = a2[j=0] = 2
59+
// [2, 1, 3]
60+
61+
int k = low; // k 临时保存低位索引
62+
int i = 0, j = 0;
63+
for (; i < n1 && j < n2; k++){
64+
// 如果 a1 与 a2 比较
65+
if (a1[i].compareTo(a2[j]) < 1) { // <=
66+
values[k] = a1[i]; // 低位数值
67+
i++;
68+
} else { // >
69+
values[k] = a2[j];
70+
j++;
71+
}
72+
}
73+
74+
// i = 2,n = 3
75+
// values[k = 0] = 2
76+
77+
// 复制 a1 剩余元素
78+
while (i < n1) {
79+
values[k] = a1[i];
80+
i++;
81+
k++;
82+
}
83+
84+
// 复制 a2 剩余元素
85+
while (j < n2) {
86+
values[k] = a2[j];
87+
j++;
88+
k++;
89+
}
90+
}
91+
92+
private void sort(T[] values, int low, int high) {
93+
94+
if (low < high) {
95+
// [3, 1, 2, 5, 4] , n = 5
96+
// low = 0
97+
// high = n-1 = 4
98+
// mid = (0+4) / 2 = 2
99+
// [0...mid] = [3, 1, 2]
100+
// [mid+1..high] = [3...4] = [5, 4]
101+
// 获取中间值
102+
int mid = (low + high) / 2;
103+
// Divide
104+
// 上半部分
105+
sort(values, low, mid);
106+
// 下半部分
107+
sort(values, mid + 1, high);
108+
// Conquer
109+
merge(values, low, mid, high);
110+
}
111+
}
112+
113+
public static void main(String[] args) {
114+
Integer[] values = Sort.of(3, 1, 2, 5, 4);
115+
Sort<Integer> sort = new MergeSort<>(); // Java 7 Diamond 语法
116+
sort.sort(values);
117+
Stream.of(values).forEach(System.out::println);
118+
}
119+
}

‎「一入 Java 深似海 」/代码/segmentfault/deep-in-java/stage-2/lesson-4/src/main/java/com/segmentfault/deep/in/java/collection/algorithm/QuickSort.java

Lines changed: 90 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,90 @@
1+
package com.segmentfault.deep.in.java.collection.algorithm;
2+
3+
import java.util.stream.Stream;
4+
5+
public class QuickSort<T extends Comparable<T>> implements Sort<T> {
6+
7+
@Override
8+
public void sort(T[] values) {
9+
int n = values.length;
10+
int low = 0;
11+
int high = n - 1;
12+
13+
// [3, 1, 2, 5, 4]
14+
// pivot = 4
15+
// => [(3, 1, 2), (4), (5)]
16+
// pIndex = 3
17+
// [0...2] = (3, 1, 2)
18+
// [3] = 4
19+
// [4] = 5
20+
21+
// [0...2] = (3, 1, 2)
22+
// pivot = 2
23+
// => [(1), (2) , (3)]
24+
// pIndex = 1
25+
// [0] = 1
26+
// [1] = 2(pivot)
27+
// [2] = 3
28+
29+
// [0] = 1, [1] = 2, [2] = 3, [3] = 4, [4] = 5
30+
31+
sort(values, low, high);
32+
}
33+
34+
private void sort(T[] values, int low, int high) {
35+
if (low < high) {
36+
// 9 -> pIndex = 5
37+
int pIndex = partition(values, low, high);
38+
// [0..4]
39+
sort(values, low, pIndex - 1);
40+
sort(values, pIndex + 1, high);
41+
}
42+
}
43+
44+
/**
45+
* 获取分区索引
46+
*
47+
* @param values 数组对象
48+
* @param low 低位索引
49+
* @param high 高位索引
50+
* @return 分区索引
51+
*/
52+
int partition(T[] values, int low, int high) {
53+
// 获取 pivot = values[high]
54+
55+
// [3, 1, 2, 5, 4]
56+
// pivot = 4
57+
// -1
58+
// [0] = 3 < 4 (0)
59+
// [1] = 1 < 4 (1)
60+
// [2] = 2 < 4 (2)
61+
// [3] = 5 > 4 (3)
62+
// => [(3, 1, 2), (4), (5)]
63+
// pIndex = 3
64+
65+
T pivot = values[high];
66+
int i = low - 1;
67+
68+
for (int j = low; j < high; j++) {
69+
if (values[j].compareTo(pivot) < 1) { // <=
70+
i++; // -1 -> 0
71+
T temp = values[i]; // 低位数据
72+
values[i] = values[j]; // 低位数据获取高位数据
73+
values[j] = temp;
74+
}
75+
}
76+
77+
T temp = values[i + 1];
78+
values[i + 1] = values[high];
79+
values[high] = temp;
80+
81+
return i + 1; // 游标+1
82+
}
83+
84+
public static void main(String[] args) {
85+
Integer[] values = Sort.of(3, 1, 2, 5, 4);
86+
Sort<Integer> sort = new QuickSort<>(); // Java 7 Diamond 语法
87+
sort.sort(values);
88+
Stream.of(values).forEach(System.out::println);
89+
}
90+
}

‎「一入 Java 深似海 」/代码/segmentfault/deep-in-java/stage-2/lesson-4/src/main/java/com/segmentfault/deep/in/java/collection/algorithm/Sort.java

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,16 @@
1+
package com.segmentfault.deep.in.java.collection.algorithm;
2+
3+
/**
4+
* 排序接口
5+
* <p>
6+
* 原地(在地)排序 - In-Place
7+
*/
8+
public interface Sort<T extends Comparable<T>> {
9+
10+
void sort(T[] values);
11+
12+
13+
static <T> T[] of(T... values) {
14+
return values;
15+
}
16+
}

‎「一入 Java 深似海 」/代码/segmentfault/deep-in-java/stage-2/pom.xml

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -16,6 +16,7 @@
1616
<module>lesson-1</module>
1717
<module>lesson-2</module>
1818
<module>lesson-3</module>
19+
<module>stage-2-lesson-4</module>
1920
</modules>
2021

2122
<build>

‎「一入 Java 深似海 」/第二期/第四节 Java 集合框架算法运用/「一入 Java 深似海 」系列课程 - 第二期 《第四节 Java 集合框架算法运用》.pdf

6.47 MB
Binary file not shown.

0 commit comments

Comments
 (0)