Skip to content

Commit fa92f53

Browse files
dunwudunwu
committed
♻️ 重构算法为泛型算法
1 parent 682da98 commit fa92f53

19 files changed

Lines changed: 192 additions & 185 deletions

File tree

‎codes/pom.xml‎

Lines changed: 5 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -59,7 +59,7 @@
5959
<!-- [Part 3] PROJECT INFO BEGIN -->
6060
<name>${artifactId}</name>
6161
<description>算法+数据结构学习笔记</description>
62-
<url>https://github.com/dunwu/algorithms-notes</url>
62+
<url>https://github.com/dunwu/algorithms</url>
6363
<inceptionYear>2016-2017</inceptionYear>
6464
<licenses>
6565
<license>
@@ -82,12 +82,12 @@
8282
<!-- [Part 4] ENVIRONMENT SETTINGS BEGIN -->
8383
<issueManagement>
8484
<system>Github</system>
85-
<url>https://github.com/dunwu/algorithms-notes/issues</url>
85+
<url>https://github.com/dunwu/algorithms/issues</url>
8686
</issueManagement>
8787
<scm>
88-
<url>https://github.com/dunwu/algorithms-notes</url>
89-
<connection>scm:git:git://github.com/dunwu/algorithms-notes.git</connection>
90-
<developerConnection>scm:git:ssh://git@github.com:dunwu/algorithms-notes.git</developerConnection>
88+
<url>https://github.com/dunwu/algorithms</url>
89+
<connection>scm:git:git://github.com/dunwu/algorithms.git</connection>
90+
<developerConnection>scm:git:ssh://git@github.com:dunwu/algorithms.git</developerConnection>
9191
</scm>
9292
<!-- [Part 4] ENVIRONMENT SETTINGS END -->
9393

‎codes/src/main/java/io/github/dunwu/algorithm/search/Search.java‎

Lines changed: 4 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -5,8 +5,9 @@
55
*/
66
public interface Search {
77
/**
8-
* 排序接口
9-
* @param list 数组
8+
* @param array 要查找的数组
9+
* @param key 要查找的 key
10+
* @return 返回第一个匹配 key 值的数组元素所在位置
1011
*/
11-
int search(int[] list, int key);
12+
<T extends Comparable<T>> int find(T array[], T key);
1213
}

‎codes/src/main/java/io/github/dunwu/algorithm/search/SearchStrategy.java‎

Lines changed: 3 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -17,11 +17,12 @@ public SearchStrategy(Search search) {
1717
this.search = search;
1818
}
1919

20-
public int search(int[] list, int key) {
20+
public int find(Integer[] list, int key) {
2121
logger.info(this.search.getClass().getSimpleName() + " 查找开始：");
2222
logger.info("要查找的线性表：{}", ArrayUtil.getArrayString(list, 0, list.length - 1));
2323
logger.info("要查找的 key：{}", key);
24-
int index = this.search.search(list, key);
24+
25+
int index = this.search.find(list, key);
2526
logger.info("{} 的位置是：{}", key, index);
2627
return index;
2728
}

‎codes/src/main/java/io/github/dunwu/algorithm/search/strategy/BinarySearch.java‎

Lines changed: 39 additions & 13 deletions
Original file line numberDiff line numberDiff line change
@@ -3,24 +3,50 @@
33
import io.github.dunwu.algorithm.search.Search;
44

55
/**
6+
* 二分查找又称折半查找，它是一种效率较高的查找方法。
7+
* 二分查找需要两个前提：(1) 必须是顺序存储结构。(2) 必须是有序的表。
8+
* 算法：
9+
* 从数据结构线形表的一端开始，顺序扫描，依次将扫描到的结点关键字与给定值k相比较，若相等则表示查找成功；
10+
* 若扫描结束仍没有找到等于关键字的结点，表示查找失败。
11+
* 算法分析：
12+
* 最坏情况 O(log n)
13+
* 最好情况 O(1)
14+
* 平均情况 O(log n)
15+
* 最坏情况下的空间复杂性 O(1)
16+
*
617
* @author Zhang Peng
7-
* @date 2018/4/18
818
*/
919
public class BinarySearch implements Search {
1020

21+
/**
22+
* 查找方法
23+
*
24+
* @param array 被查找的线性表
25+
* @param key 被查找的 key
26+
* @return 成功返回 key 的位置；失败返回 -1
27+
*/
1128
@Override
12-
public int search(int[] list, int key) {
13-
int low = 0, mid = 0, high = list.length - 1;
14-
while (low <= high) {
15-
mid = (low + high) / 2;
16-
if (list[mid] == key) {
17-
return mid; // 查找成功，直接返回位置
18-
} else if (list[mid] < key) {
19-
low = mid + 1; // 关键字大于中间位置的值，则在大值区间[mid+1, high]继续查找
20-
} else {
21-
high = mid - 1; // 关键字小于中间位置的值，则在小值区间[low, mid-1]继续查找
22-
}
29+
public <T extends Comparable<T>> int find(T array[], T key) {
30+
return search(array, key, 0, array.length);
31+
}
32+
33+
private <T extends Comparable<T>> int search(T array[], T key, int left, int right) {
34+
// this means that the key not found
35+
if (right < left) {
36+
return -1;
37+
}
38+
39+
int mid = (left + right) >>> 1;
40+
int comp = key.compareTo(array[mid]);
41+
42+
if (comp < 0) {
43+
return search(array, key, left, mid - 1);
44+
}
45+
46+
if (comp > 0) {
47+
return search(array, key, mid + 1, right);
2348
}
24-
return -1;
49+
50+
return mid;
2551
}
2652
}

‎codes/src/main/java/io/github/dunwu/algorithm/search/strategy/OrderSearch.java‎

Lines changed: 20 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -3,21 +3,34 @@
33
import io.github.dunwu.algorithm.search.Search;
44

55
/**
6+
* 顺序查找是一种最简单的查找算法。它的查找效率不高。
7+
* 算法：
8+
* 从数据结构线形表的一端开始，顺序扫描，依次将扫描到的结点关键字与给定值k相比较，若相等则表示查找成功；
9+
* 若扫描结束仍没有找到关键字等于k的结点，表示查找失败。
10+
* 算法分析：
11+
* 最坏情况 O(n)
12+
* 最好情况 O(1)
13+
* 平均情况 O(n)
14+
* 最坏情况下的空间复杂性
15+
*
616
* @author Zhang Peng
7-
* @date 2018/4/18
817
*/
918
public class OrderSearch implements Search {
1019

20+
/**
21+
* 查找方法
22+
*
23+
* @param array 被查找的线性表
24+
* @param key 被查找的 key
25+
* @return 成功返回 key 的位置；失败返回 -1
26+
*/
1127
@Override
12-
public int search(int[] list, int key) {
13-
// 从前往后扫描list数组，如果有元素的值与key相等，直接返回其位置
14-
for (int i = 0; i < list.length; i++) {
15-
if (key == list[i]) {
28+
public <T extends Comparable<T>> int find(T[] array, T key) {
29+
for (int i = 0; i < array.length; i++) {
30+
if (array[i].compareTo(key) == 0) {
1631
return i;
1732
}
1833
}
19-
20-
// 如果扫描完，说明没有元素的值匹配key，返回-1，表示查找失败
2134
return -1;
2235
}
2336
}

‎codes/src/main/java/io/github/dunwu/algorithm/sort/Sort.java‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -6,7 +6,7 @@
66
public interface Sort {
77
/**
88
* 排序接口
9-
* @param list 数组
9+
* @param list 要排序的数组
1010
*/
11-
void sort(int[] list);
11+
<T extends Comparable<T>> void sort(T[] list);
1212
}

‎codes/src/main/java/io/github/dunwu/algorithm/sort/SortStrategy.java‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -16,7 +16,7 @@ public SortStrategy(Sort sort) {
1616
this.sort = sort;
1717
}
1818

19-
public void sort(int[] list) {
19+
public void sort(Integer[] list) {
2020
logger.info(this.sort.getClass().getSimpleName() + " 排序开始：");
2121
logger.info("排序前: {}", ArrayUtil.getArrayString(list, 0, list.length - 1));
2222
this.sort.sort(list);

‎codes/src/main/java/io/github/dunwu/algorithm/sort/strategy/BubbleSort.java‎

Lines changed: 3 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -9,17 +9,14 @@
99
*/
1010
public class BubbleSort implements Sort {
1111
@Override
12-
public void sort(int[] list) {
13-
// 用来交换的临时数
14-
int temp = 0;
15-
12+
public <T extends Comparable<T>> void sort(T[] list) {
1613
// 要遍历的次数
1714
for (int i = 0; i < list.length - 1; i++) {
1815
// 从后向前依次的比较相邻两个数的大小，遍历一次后，把数组中第i小的数放在第i个位置上
1916
for (int j = list.length - 1; j > i; j--) {
2017
// 比较相邻的元素，如果前面的数大于后面的数，则交换
21-
if (list[j - 1] > list[j]) {
22-
temp = list[j - 1];
18+
if (list[j - 1].compareTo(list[j]) > 0) {
19+
T temp = list[j - 1];
2320
list[j - 1] = list[j];
2421
list[j] = temp;
2522
}

‎codes/src/main/java/io/github/dunwu/algorithm/sort/strategy/BubbleSort2.java‎

Lines changed: 3 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -9,9 +9,7 @@
99
*/
1010
public class BubbleSort2 implements Sort {
1111
@Override
12-
public void sort(int[] list) {
13-
// 用来交换的临时数
14-
int temp = 0;
12+
public <T extends Comparable<T>> void sort(T[] list) {
1513
// 交换标志
1614
boolean bChange = false;
1715

@@ -21,8 +19,8 @@ public void sort(int[] list) {
2119
// 从后向前依次的比较相邻两个数的大小，遍历一次后，把数组中第i小的数放在第i个位置上
2220
for (int j = list.length - 1; j > i; j--) {
2321
// 比较相邻的元素，如果前面的数大于后面的数，则交换
24-
if (list[j - 1] > list[j]) {
25-
temp = list[j - 1];
22+
if (list[j - 1].compareTo(list[j]) > 0) {
23+
T temp = list[j - 1];
2624
list[j - 1] = list[j];
2725
list[j] = temp;
2826
bChange = true;

‎codes/src/main/java/io/github/dunwu/algorithm/sort/strategy/HeapSort.java‎

Lines changed: 6 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -8,20 +8,20 @@
88
* @author Zhang Peng
99
*/
1010
public class HeapSort implements Sort {
11-
private static void adjustHeat(int[] array, int parent, int length) {
11+
private static <T extends Comparable<T>> void adjustHeat(T[] array, int parent, int length) {
1212
// temp保存当前父节点
13-
int temp = array[parent];
13+
T temp = array[parent];
1414
// 先获得左孩子
1515
int child = 2 * parent + 1;
1616

1717
while (child < length) {
1818
// 如果有右孩子结点，并且右孩子结点的值大于左孩子结点，则选取右孩子结点
19-
if (child + 1 < length && array[child] < array[child + 1]) {
19+
if (child + 1 < length && array[child].compareTo(array[child + 1]) < 0) {
2020
child++;
2121
}
2222

2323
// 如果父结点的值已经大于孩子结点的值，则直接结束
24-
if (temp >= array[child]) {
24+
if (temp.compareTo(array[child]) >= 0) {
2525
break;
2626
}
2727

@@ -37,7 +37,7 @@ private static void adjustHeat(int[] array, int parent, int length) {
3737
}
3838

3939
@Override
40-
public void sort(int[] list) {
40+
public <T extends Comparable<T>> void sort(T[] list) {
4141
// 循环建立初始堆
4242
for (int i = list.length / 2; i >= 0; i--) {
4343
adjustHeat(list, i, list.length);
@@ -46,7 +46,7 @@ public void sort(int[] list) {
4646
// 进行n-1次循环，完成排序
4747
for (int i = list.length - 1; i > 0; i--) {
4848
// 最后一个元素和第一元素进行交换
49-
int temp = list[i];
49+
T temp = list[i];
5050
list[i] = list[0];
5151
list[0] = temp;
5252

0 commit comments

Comments
 (0)