Skip to content

Commit db2ce4c

Browse files
Jack_Zhanggitee-org
Jack_Zhang
authored and
gitee-org
committed
!2 归并算法与Master表达式
Merge pull request !2 from Jack_Zhang/temp
2 parents 74c694d + 7c86948 commit db2ce4c

6 files changed

Lines changed: 122 additions & 1 deletion

File tree

‎.gitignore‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -7,4 +7,5 @@
77
.idea/modules.xml
88
.idea/vcs.xml
99
.idea/
10+
out/
1011

‎README.md‎

Lines changed: 12 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -15,7 +15,18 @@ https://visualgo.net/
1515
##### 1.选择排序 SelectSortDemo
1616
##### 2.冒泡排序 BubbleSortDemo
1717
##### 3.插入排序 InsertSortDemo
18-
18+
Master表达式推导
19+
T(N) = a*T(N/b) + O(N^d)
20+
1) log(b,a) > d 时间复杂度为 O(N^log(b,a))
21+
2) log(b,a) = d 时间复杂度为 O(N^d * logN)
22+
3) log(b,a) < d 时间复杂度为 O(N^d)
23+
归并排序可通过该表达式推出时间复杂度
24+
仅查看递归方法 {@link #process} 的一层即可，不需要看递归多层计算
25+
可得 Master 表达式为
26+
T(N) = 2 * T(N/2) + O(N^1)
27+
a = 2, b = 2,d = 1
28+
log(2,2) = 1
29+
可得出时间复杂度为 O(N * logN)
1930

2031
#### 参与贡献
2132

‎src/com/basic/InsertSortDemo.java‎

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -15,6 +15,9 @@ public class InsertSortDemo {
1515
/**
1616
* <p>
1717
* 插入排序代码实现
18+
* TODO 注意选择排序与插入排序的不同，
19+
* 选择排序是在i位置后选择第i个最小/大的值插入到i位置，
20+
* 插入排序是将第i位值向前移动，类似与冒泡，找到合适的位置，使得i位置之前数据是有序的。
1821
* <p/>
1922
* @param arr 未排序数组
2023
* @return int[] 排序后数组

‎src/com/basic/MergeSortDemo.java‎

Lines changed: 81 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,81 @@
1+
package com.basic;
2+
3+
import com.utils.VerifyUtil;
4+
5+
/**
6+
* @ClassName: MergeSortDemo
7+
* @Author: Jack.Zhang
8+
* @link <a href = "mailto:[email protected]">联系作者<a/>
9+
* @Description: #归并排序 代码演示
10+
* @Date: 2021-11-22
11+
*/
12+
public class MergeSortDemo {
13+
14+
15+
/**
16+
* <p>
17+
* 归并排序,时间复杂度为 O(N*logN) 空间复杂度为O(N)
18+
* TODO Master 表达式推导归并排序时间复杂度
19+
* T(N) = a*T(N/b) + O(N^d)
20+
* 1) log(b,a) > d 时间复杂度为 O(N^log(b,a))
21+
* 2) log(b,a) = d 时间复杂度为 O(N^d * logN)
22+
* 3) log(b,a) < d 时间复杂度为 O(N^d)
23+
* 归并排序可通过该表达式推出时间复杂度
24+
* 仅查看递归方法 {@link #process} 的一层即可，不需要看递归多层计算
25+
* 可得 Master 表达式为
26+
* T(N) = 2 * T(N/2) + O(N^1)
27+
* a = 2, b = 2,d = 1
28+
* log(2,2) = 1
29+
* 可得出时间复杂度为 O(N * logN)
30+
* <p/>
31+
* @param arr
32+
* @return int[]
33+
* @author Jack.Zhang 2021/11/23 13:53
34+
* @link <a href = "mailto:[email protected]">联系作者<a/>
35+
* @since 1.0.0
36+
* @see
37+
*/
38+
public static int[] mergeSort(int[] arr) {
39+
if (arr == null || arr.length == 0) return arr;
40+
int mid = arr.length >> 1;
41+
int end = arr.length - 1;
42+
process(arr, 0, mid);
43+
process(arr, mid + 1, end);
44+
merge(arr, 0, end, mid);
45+
return arr;
46+
}
47+
48+
private static void process(int[] arr, int left, int right) {
49+
if (arr == null || arr.length == 0) return;
50+
if (left < right) {
51+
int mid = left + ((right - left) >> 1);
52+
process(arr, left, mid);
53+
process(arr, mid + 1, right);
54+
merge(arr, left, right, mid);
55+
}
56+
}
57+
58+
private static void merge(int[] arr, int start, int end, int mid) {
59+
if (start == end)return;
60+
int[] temp = new int[end - start + 1];
61+
int leftArrIndex = start;
62+
int rightArrIndex = mid + 1;
63+
int index = 0;
64+
while (leftArrIndex <= mid && rightArrIndex <= end)
65+
temp[index++] = arr[leftArrIndex] > arr[rightArrIndex] ? arr[rightArrIndex++] : arr[leftArrIndex++];
66+
while (leftArrIndex <= mid)
67+
temp[index++] = arr[leftArrIndex++];
68+
while (rightArrIndex <= end)
69+
temp[index++] = arr[rightArrIndex++];
70+
for (int i = start, j = 0; i <= end; i++) {
71+
arr[i] = temp[j++];
72+
}
73+
}
74+
75+
76+
public static void main(String[] args) {
77+
boolean verify = VerifyUtil.verify(MergeSortDemo::mergeSort, true);
78+
System.out.println(verify);
79+
80+
}
81+
}

‎src/com/basic/SelectSortDemo.java‎

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -15,6 +15,9 @@ public class SelectSortDemo {
1515
/**
1616
* <p>
1717
* 选择算法逻辑代码。时间最优时间复杂度为 O(n^2),最坏负杂度为O(n^2),空间复杂度为O(1)
18+
* TODO 注意选择排序与插入排序的不同，
19+
* 选择排序是在i位置后选择第i个最小/大的值插入到i位置，
20+
* 插入排序是将第i位值向前移动，类似与冒泡，找到合适的位置，使得i位置之前数据是有序的。
1821
* <p/>
1922
* @param arr
2023
* @return int[]

‎src/com/utils/VerifyUtil.java‎

Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -33,6 +33,10 @@ private VerifyUtil() {
3333
* 生成最大数值
3434
*/
3535
private static final int GENERATE_MAX_VALUE = 1000;
36+
/** 是否打印比对情况,自己控制是否打印比对情况 */
37+
private final static boolean WHETHER_TO_PRINT_THE_COMPARISON = true;
38+
/** 分隔符 */
39+
private final static String DELIMITER = "-------------------------------------------------------------------------";
3640

3741
/**
3842
* <p>
@@ -50,17 +54,23 @@ private VerifyUtil() {
5054
public static boolean verify(final Function<List<Number>, List<Number>> sortFunction,
5155
boolean isAsc, boolean isFloat) {
5256
for (int i = 0; i < VERIFY_COUNT; i++) {
57+
if (WHETHER_TO_PRINT_THE_COMPARISON)
58+
System.out.println(DELIMITER);
5359
// 1.生成数组
5460
List<Number> generationDataList = IntStream.rangeClosed(1, GENERATE_COUNT).parallel().mapToObj(v -> {
5561
return isFloat ? (GENERATE_MAX_VALUE * Math.random()) : (int) (GENERATE_MAX_VALUE * Math.random());
5662
}).collect(Collectors.toList());
5763
// 2.算法排序得出结果
5864
List<Number> sortResult = sortFunction.apply(generationDataList);
65+
if (WHETHER_TO_PRINT_THE_COMPARISON)
66+
System.out.println("算法排序结果为："+sortResult);
5967
// 3.正确的排序结果
6068
List<Number> successAscList = generationDataList.stream()
6169
.sorted().collect(Collectors.toList());
6270
if (!isAsc)
6371
Collections.reverse(successAscList);
72+
if (WHETHER_TO_PRINT_THE_COMPARISON)
73+
System.out.println("正确排序结果为："+successAscList);
6474
boolean success = compareTwoSets(sortResult, successAscList);
6575
if (!success) {
6676
// 自己写的算法排序结果错误
@@ -87,7 +97,10 @@ public static boolean verify(final Function<List<Number>, List<Number>> sortFunc
8797
*/
8898
public static boolean verify(final Function<int[], int[]> sortFunction,
8999
boolean isAsc) {
100+
long startTime = System.currentTimeMillis();
90101
for (int i = 0; i < VERIFY_COUNT; i++) {
102+
if (WHETHER_TO_PRINT_THE_COMPARISON)
103+
System.out.println(DELIMITER);
91104
int[] generateArr = new int[GENERATE_COUNT];
92105
List<Integer> generateList = new ArrayList<>(GENERATE_COUNT);
93106
for (int j = 0; j < GENERATE_COUNT; j++) {
@@ -99,16 +112,25 @@ public static boolean verify(final Function<int[], int[]> sortFunction,
99112
for (int sortResult : sortResults) {
100113
sortList.add(sortResult);
101114
}
115+
if (WHETHER_TO_PRINT_THE_COMPARISON)
116+
System.out.println("算法排序结果为："+sortList);
102117
Collections.sort(generateList);
103118
if (!isAsc)
104119
Collections.reverse(generateList);
120+
if (WHETHER_TO_PRINT_THE_COMPARISON)
121+
System.out.println("正确排序结果为："+generateList);
105122
boolean success = compareTwoSets(sortList, generateList);
106123
if (!success) {
107124
System.out.println("自己写的算法排序结果为：\r\n"+sortList);
108125
System.out.println("正确排序结果为：\r\n"+generateList);
109126
return success;
110127
}
111128
}
129+
long millisecond = (System.currentTimeMillis() - startTime);
130+
System.out.println("验证结果次数："+VERIFY_COUNT+"次\t"+"数组大小："+GENERATE_COUNT+"个元素");
131+
System.out.println("总耗时："+millisecond+"毫秒");
132+
System.out.println("总耗时："+millisecond/1000+"秒");
133+
112134
return true;
113135
}
114136

0 commit comments

Comments
 (0)