Skip to content

Commit fa0d195

Browse files
dunwudunwu
committed
👌 针对排序算法代码做简单优化
1 parent 4fb72b6 commit fa0d195

14 files changed

Lines changed: 203 additions & 69 deletions

File tree

‎codes/pom.xml‎

Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -16,6 +16,21 @@
1616

1717
<!-- RELATIONSHIP SETTINGS BEGIN -->
1818
<dependencies>
19+
<dependency>
20+
<groupId>org.slf4j</groupId>
21+
<artifactId>slf4j-api</artifactId>
22+
<version>1.7.25</version>
23+
</dependency>
24+
<dependency>
25+
<groupId>ch.qos.logback</groupId>
26+
<artifactId>logback-classic</artifactId>
27+
<version>1.1.3</version>
28+
</dependency>
29+
<dependency>
30+
<groupId>ch.qos.logback</groupId>
31+
<artifactId>logback-core</artifactId>
32+
<version>1.1.3</version>
33+
</dependency>
1934
<dependency>
2035
<groupId>junit</groupId>
2136
<artifactId>junit</artifactId>

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

Lines changed: 47 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -1,36 +1,52 @@
11
package io.github.dunwu.algorithm.sort;
22

3+
import org.slf4j.Logger;
4+
import org.slf4j.LoggerFactory;
5+
36
import java.util.Random;
47

58
/**
69
* @author Zhang Peng
710
*/
811
public class ArrayUtil {
9-
public static void printArray(int[] list, int begin, int end) {
12+
private static final Logger logger = LoggerFactory.getLogger(ArrayUtil.class);
13+
14+
public static void debugLogArray(int[] list, int begin, int end, String tip) {
15+
String content = tip + getArrayString(list, begin, end);
16+
if (logger.isDebugEnabled()) {
17+
logger.debug(content);
18+
}
19+
}
20+
21+
public static String getArrayString(int[] list, int begin, int end) {
22+
StringBuilder sb = new StringBuilder();
23+
sb.append("\n");
1024
for (int i = 0; i < begin; i++) {
11-
System.out.print("\t");
25+
sb.append("\t");
1226
}
1327
int count = 0;
1428
for (int i = begin; i <= end; i++) {
15-
System.out.print(list[i] + "\t");
29+
sb.append(list[i] + "\t");
1630
if (++count == 10) {
17-
System.out.println();
31+
sb.append("\n");
1832
count = 0;
1933
}
2034
}
21-
System.out.println();
35+
36+
return sb.toString();
2237
}
2338

2439
/**
25-
* 随机指定范围内N个不重复的数 在初始化的无重复待选数组中随机产生一个数放入结果中， 将待选数组被随机到的数，用待选数组(len-1)下标对应的数替换
26-
* 然后从len-2里随机产生下一个随机数，如此类推
27-
*
28-
* @param max 指定范围最大值
40+
* 随机指定范围内N个不重复的数。
41+
* <p>在初始化的无重复待选数组中随机产生一个数放入结果中，</p>
42+
* <p>将待选数组被随机到的数，用待选数组(len-1)下标对应的数替换，</p>
43+
* <p>然后从len-2里随机产生下一个随机数，如此类推</p>
2944
* @param min 指定范围最小值
45+
* @param max 指定范围最大值
3046
* @param length 随机数个数
3147
* @return int[] 随机数结果集
3248
*/
33-
public static int[] randomArray(int min, int max, int length) {
49+
public static int[] randomNoRepeatArray(int min, int max, int length) {
3450
int len = max - min + 1;
3551

3652
if (max < min || length > len) {
@@ -56,4 +72,25 @@ public static int[] randomArray(int min, int max, int length) {
5672
}
5773
return result;
5874
}
75+
76+
/**
77+
* 随机指定范围内N个重复的数。
78+
* @param min 指定范围最小值
79+
* @param max 指定范围最大值
80+
* @param length 随机数个数
81+
* @return 随机数结果集
82+
*/
83+
public static int[] randomRepeatArray(int min, int max, int length) {
84+
int len = max - min + 1;
85+
86+
if (max < min || length > len) {
87+
return null;
88+
}
89+
90+
int[] result = new int[length];
91+
for (int i = 0; i < result.length; i++) {
92+
result[i] = (int) (Math.random() * max);
93+
}
94+
return result;
95+
}
5996
}

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

Lines changed: 7 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -1,21 +1,24 @@
11
package io.github.dunwu.algorithm.sort;
22

3+
import org.slf4j.Logger;
4+
import org.slf4j.LoggerFactory;
5+
36
/**
47
* 使用策略模式，对算法进行包装
58
* @author Zhang Peng
69
*/
710
public class SortStrategy {
811
private Sort sort;
12+
private static final Logger logger = LoggerFactory.getLogger(SortStrategy.class);
913

1014
public SortStrategy(Sort sort) {
1115
this.sort = sort;
1216
}
1317

1418
public void sort(int[] list) {
15-
System.out.print("排序前:\n");
16-
ArrayUtil.printArray(list, 0, list.length - 1);
19+
logger.info(this.sort.getClass().getSimpleName() + " 排序开始：");
20+
logger.info("排序前: {}", ArrayUtil.getArrayString(list, 0, list.length - 1));
1721
this.sort.sort(list);
18-
System.out.print("排序后:\n");
19-
ArrayUtil.printArray(list, 0, list.length - 1);
22+
logger.info("排序后: {}", ArrayUtil.getArrayString(list, 0, list.length - 1));
2023
}
2124
}

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

Lines changed: 5 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -3,6 +3,10 @@
33
import io.github.dunwu.algorithm.sort.ArrayUtil;
44
import io.github.dunwu.algorithm.sort.Sort;
55

6+
/**
7+
* 冒泡排序算法
8+
* @author Zhang Peng
9+
*/
610
public class BubbleSort implements Sort {
711
@Override
812
public void sort(int[] list) {
@@ -21,8 +25,7 @@ public void sort(int[] list) {
2125
}
2226
}
2327

24-
System.out.format("第 %d 趟：\n", i);
25-
ArrayUtil.printArray(list, 0, list.length - 1);
28+
ArrayUtil.debugLogArray(list, 0, list.length - 1, String.format("第 %d 趟：", i + 1));
2629
}
2730
}
2831
}

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

Lines changed: 1 addition & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -5,7 +5,6 @@
55

66
/**
77
* 冒泡排序的优化算法
8-
*
98
* @author Zhang Peng
109
*/
1110
public class BubbleSort2 implements Sort {
@@ -35,8 +34,7 @@ public void sort(int[] list) {
3534
break;
3635
}
3736

38-
System.out.format("第 %d 趟：\n", i);
39-
ArrayUtil.printArray(list, 0, list.length - 1);
37+
ArrayUtil.debugLogArray(list, 0, list.length - 1, String.format("第 %d 趟：", i + 1));
4038
}
4139
}
4240
}

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

Lines changed: 6 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -3,6 +3,10 @@
33
import io.github.dunwu.algorithm.sort.ArrayUtil;
44
import io.github.dunwu.algorithm.sort.Sort;
55

6+
/**
7+
* 堆排序算法
8+
* @author Zhang Peng
9+
*/
610
public class HeapSort implements Sort {
711
private static void heapadjust(int[] array, int parent, int length) {
812
// temp保存当前父节点
@@ -48,8 +52,8 @@ public void sort(int[] list) {
4852

4953
// 筛选 R[0] 结点，得到i-1个结点的堆
5054
heapadjust(list, 0, i);
51-
System.out.format("第 %d 趟: \n", list.length - i);
52-
ArrayUtil.printArray(list, 0, list.length - 1);
55+
56+
ArrayUtil.debugLogArray(list, 0, list.length - 1, String.format("第 %d 趟：", list.length - i));
5357
}
5458
}
5559
}

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

Lines changed: 6 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -3,12 +3,15 @@
33
import io.github.dunwu.algorithm.sort.ArrayUtil;
44
import io.github.dunwu.algorithm.sort.Sort;
55

6+
/**
7+
* 插入排序算法
8+
* @author Zhang Peng
9+
*/
610
public class InsertSort implements Sort {
711
@Override
812
public void sort(int[] list) {
913
// 打印第一个元素
10-
System.out.format("i = %d:\t", 0);
11-
ArrayUtil.printArray(list, 0, 0);
14+
ArrayUtil.debugLogArray(list, 0, 0, String.format("i = %d:\t", 0));
1215

1316
// 第1个数肯定是有序的，从第2个数开始遍历，依次插入有序序列
1417
for (int i = 1; i < list.length; i++) {
@@ -22,8 +25,7 @@ public void sort(int[] list) {
2225
}
2326
list[j + 1] = temp;
2427

25-
System.out.format("i = %d:\t", i);
26-
ArrayUtil.printArray(list, 0, i);
28+
ArrayUtil.debugLogArray(list, 0, list.length - 1, String.format("i = %d:\t", i));
2729
}
2830
}
2931
}

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

Lines changed: 1 addition & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -66,8 +66,7 @@ private void mergepass(int[] array, int gap, int length) {
6666
public void sort(int[] list) {
6767
for (int gap = 1; gap < list.length; gap = 2 * gap) {
6868
mergepass(list, gap, list.length);
69-
System.out.print("gap = " + gap + ":\n");
70-
ArrayUtil.printArray(list, 0, list.length - 1);
69+
ArrayUtil.debugLogArray(list, 0, list.length - 1, String.format("gap = %d", gap));
7170
}
7271
}
7372

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

Lines changed: 5 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -3,6 +3,10 @@
33
import io.github.dunwu.algorithm.sort.ArrayUtil;
44
import io.github.dunwu.algorithm.sort.Sort;
55

6+
/**
7+
* 快速排序算法
8+
* @author Zhang Peng
9+
*/
610
public class QuickSort implements Sort {
711

812
private int division(int[] list, int left, int right) {
@@ -37,8 +41,7 @@ private void quickSort(int[] list, int left, int right) {
3741
// 对数组进行分割，取出下次分割的基准标号
3842
int base = division(list, left, right);
3943

40-
System.out.format("base = %d:\n", list[base]);
41-
ArrayUtil.printArray(list, left, right);
44+
ArrayUtil.debugLogArray(list, left, right, String.format("base = %d: ", list[base]));
4245

4346
// 对“基准标号“左侧的一组数值进行递归的切割，以至于将这些数值完整的排序
4447
quickSort(list, left, base - 1);

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

Lines changed: 5 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -2,18 +2,21 @@
22

33
import io.github.dunwu.algorithm.sort.Sort;
44

5+
/**
6+
* 基数排序算法
7+
* @author Zhang Peng
8+
*/
59
public class RadixSort implements Sort {
610

711
/**
812
* 获取x这个数的d位数上的数字，比如获取123的1位数，结果返回3
9-
*
1013
* @param x
1114
* @param d
1215
* @return
1316
*/
1417
private int getDigit(int x, int d) {
1518
// 本实例中的最大数是百位数，所以只要到100就可以了
16-
int[] a = {1, 1, 10, 100};
19+
int[] a = { 1, 1, 10, 100 };
1720
return ((x / a[d]) % 10);
1821
}
1922

0 commit comments

Comments
 (0)