Skip to content

Commit 4fb72b6

Browse files
dunwudunwu
committed
✨ 添加排序算法以及单元测试
1 parent a60f959 commit 4fb72b6

File tree

14 files changed

+715
-0
lines changed

14 files changed

+715
-0
lines changed

‎codes/pom.xml‎

Lines changed: 80 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,80 @@
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+
<modelVersion>4.0.0</modelVersion>
6+
7+
8+
<!-- [Part 1] BASIC SETTINGS BEGIN -->
9+
10+
<!-- MAVEN COORDINATE BEGIN -->
11+
<groupId>io.github.dunwu</groupId>
12+
<artifactId>algorithms-notes</artifactId>
13+
<version>1.0.1</version>
14+
<packaging>jar</packaging>
15+
<!-- MAVEN COORDINATE END -->
16+
17+
<!-- RELATIONSHIP SETTINGS BEGIN -->
18+
<dependencies>
19+
<dependency>
20+
<groupId>junit</groupId>
21+
<artifactId>junit</artifactId>
22+
<version>4.12</version>
23+
<scope>test</scope>
24+
</dependency>
25+
</dependencies>
26+
<!-- RELATIONSHIP SETTINGS END -->
27+
28+
<!-- PROPERTIES BEGIN -->
29+
<properties>
30+
<project.build.sourceEncoding>UTF-8</project.build.sourceEncoding>
31+
<java.version>1.6</java.version>
32+
<maven.compiler.source>${java.version}</maven.compiler.source>
33+
<maven.compiler.target>${java.version}</maven.compiler.target>
34+
</properties>
35+
<!-- PROPERTIES END -->
36+
37+
<!-- [Part 1] BASIC SETTINGS END -->
38+
39+
40+
<!-- [Part 2] BUILD SETTINGS BEGIN -->
41+
<!-- [Part 2] BUILD SETTINGS END -->
42+
43+
44+
<!-- [Part 3] PROJECT INFO BEGIN -->
45+
<name>${project.artifactId}</name>
46+
<description>算法+数据结构学习笔记</description>
47+
<url>https://github.com/dunwu/algorithms-notes</url>
48+
<inceptionYear>2016-2017</inceptionYear>
49+
<licenses>
50+
<license>
51+
<name>Apache License, Version 2.0</name>
52+
<url>https://www.apache.org/licenses/LICENSE-2.0.txt</url>
53+
<distribution>repo</distribution>
54+
<comments>A business-friendly OSS license</comments>
55+
</license>
56+
</licenses>
57+
<developers>
58+
<developer>
59+
<name>Zhang Peng</name>
60+
<email>forbreak@163.com</email>
61+
<timezone>+8</timezone>
62+
</developer>
63+
</developers>
64+
<!-- [Part 3] PROJECT INFO END -->
65+
66+
67+
<!-- [Part 4] ENVIRONMENT SETTINGS BEGIN -->
68+
<issueManagement>
69+
<system>Github</system>
70+
<url>https://github.com/dunwu/algorithms-notes/issues</url>
71+
</issueManagement>
72+
<scm>
73+
<url>https://github.com/dunwu/algorithms-notes</url>
74+
<connection>scm:git:git://github.com/dunwu/algorithms-notes.git</connection>
75+
<developerConnection>scm:git:ssh://git@github.com:dunwu/algorithms-notes.git</developerConnection>
76+
</scm>
77+
<!-- [Part 4] ENVIRONMENT SETTINGS END -->
78+
79+
80+
</project>

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

Lines changed: 59 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,59 @@
1+
package io.github.dunwu.algorithm.sort;
2+
3+
import java.util.Random;
4+
5+
/**
6+
* @author Zhang Peng
7+
*/
8+
public class ArrayUtil {
9+
public static void printArray(int[] list, int begin, int end) {
10+
for (int i = 0; i < begin; i++) {
11+
System.out.print("\t");
12+
}
13+
int count = 0;
14+
for (int i = begin; i <= end; i++) {
15+
System.out.print(list[i] + "\t");
16+
if (++count == 10) {
17+
System.out.println();
18+
count = 0;
19+
}
20+
}
21+
System.out.println();
22+
}
23+
24+
/**
25+
* 随机指定范围内N个不重复的数 在初始化的无重复待选数组中随机产生一个数放入结果中， 将待选数组被随机到的数，用待选数组(len-1)下标对应的数替换
26+
* 然后从len-2里随机产生下一个随机数，如此类推
27+
*
28+
* @param max 指定范围最大值
29+
* @param min 指定范围最小值
30+
* @param length 随机数个数
31+
* @return int[] 随机数结果集
32+
*/
33+
public static int[] randomArray(int min, int max, int length) {
34+
int len = max - min + 1;
35+
36+
if (max < min || length > len) {
37+
return null;
38+
}
39+
40+
// 初始化给定范围的待选数组
41+
int[] source = new int[len];
42+
for (int i = min; i < min + len; i++) {
43+
source[i - min] = i;
44+
}
45+
46+
int[] result = new int[length];
47+
Random rd = new Random();
48+
int index = 0;
49+
for (int i = 0; i < result.length; i++) {
50+
// 待选数组0到(len-2)随机一个下标
51+
index = Math.abs(rd.nextInt() % len--);
52+
// 将随机到的数放入结果集
53+
result[i] = source[index];
54+
// 将待选数组中被随机到的数，用待选数组(len-1)下标对应的数替换
55+
source[index] = source[len];
56+
}
57+
return result;
58+
}
59+
}

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

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,12 @@
1+
package io.github.dunwu.algorithm.sort;
2+
3+
/**
4+
* @author Zhang Peng
5+
*/
6+
public interface Sort {
7+
/**
8+
* 排序接口
9+
* @param list 数组
10+
*/
11+
void sort(int[] list);
12+
}

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

Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
package io.github.dunwu.algorithm.sort;
2+
3+
/**
4+
* 使用策略模式，对算法进行包装
5+
* @author Zhang Peng
6+
*/
7+
public class SortStrategy {
8+
private Sort sort;
9+
10+
public SortStrategy(Sort sort) {
11+
this.sort = sort;
12+
}
13+
14+
public void sort(int[] list) {
15+
System.out.print("排序前:\n");
16+
ArrayUtil.printArray(list, 0, list.length - 1);
17+
this.sort.sort(list);
18+
System.out.print("排序后:\n");
19+
ArrayUtil.printArray(list, 0, list.length - 1);
20+
}
21+
}

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

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
package io.github.dunwu.algorithm.sort.strategy;
2+
3+
import io.github.dunwu.algorithm.sort.ArrayUtil;
4+
import io.github.dunwu.algorithm.sort.Sort;
5+
6+
public class BubbleSort implements Sort {
7+
@Override
8+
public void sort(int[] list) {
9+
// 用来交换的临时数
10+
int temp = 0;
11+
12+
// 要遍历的次数
13+
for (int i = 0; i < list.length - 1; i++) {
14+
// 从后向前依次的比较相邻两个数的大小，遍历一次后，把数组中第i小的数放在第i个位置上
15+
for (int j = list.length - 1; j > i; j--) {
16+
// 比较相邻的元素，如果前面的数大于后面的数，则交换
17+
if (list[j - 1] > list[j]) {
18+
temp = list[j - 1];
19+
list[j - 1] = list[j];
20+
list[j] = temp;
21+
}
22+
}
23+
24+
System.out.format("第 %d 趟：\n", i);
25+
ArrayUtil.printArray(list, 0, list.length - 1);
26+
}
27+
}
28+
}

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

Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
package io.github.dunwu.algorithm.sort.strategy;
2+
3+
import io.github.dunwu.algorithm.sort.ArrayUtil;
4+
import io.github.dunwu.algorithm.sort.Sort;
5+
6+
/**
7+
* 冒泡排序的优化算法
8+
*
9+
* @author Zhang Peng
10+
*/
11+
public class BubbleSort2 implements Sort {
12+
@Override
13+
public void sort(int[] list) {
14+
// 用来交换的临时数
15+
int temp = 0;
16+
// 交换标志
17+
boolean bChange = false;
18+
19+
// 要遍历的次数
20+
for (int i = 0; i < list.length - 1; i++) {
21+
bChange = false;
22+
// 从后向前依次的比较相邻两个数的大小，遍历一次后，把数组中第i小的数放在第i个位置上
23+
for (int j = list.length - 1; j > i; j--) {
24+
// 比较相邻的元素，如果前面的数大于后面的数，则交换
25+
if (list[j - 1] > list[j]) {
26+
temp = list[j - 1];
27+
list[j - 1] = list[j];
28+
list[j] = temp;
29+
bChange = true;
30+
}
31+
}
32+
33+
// 如果标志为false，说明本轮遍历没有交换，已经是有序数列，可以结束排序
34+
if (false == bChange) {
35+
break;
36+
}
37+
38+
System.out.format("第 %d 趟：\n", i);
39+
ArrayUtil.printArray(list, 0, list.length - 1);
40+
}
41+
}
42+
}

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

Lines changed: 55 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,55 @@
1+
package io.github.dunwu.algorithm.sort.strategy;
2+
3+
import io.github.dunwu.algorithm.sort.ArrayUtil;
4+
import io.github.dunwu.algorithm.sort.Sort;
5+
6+
public class HeapSort implements Sort {
7+
private static void heapadjust(int[] array, int parent, int length) {
8+
// temp保存当前父节点
9+
int temp = array[parent];
10+
// 先获得左孩子
11+
int child = 2 * parent + 1;
12+
13+
while (child < length) {
14+
// 如果有右孩子结点，并且右孩子结点的值大于左孩子结点，则选取右孩子结点
15+
if (child + 1 < length && array[child] < array[child + 1]) {
16+
child++;
17+
}
18+
19+
// 如果父结点的值已经大于孩子结点的值，则直接结束
20+
if (temp >= array[child]) {
21+
break;
22+
}
23+
24+
// 把孩子结点的值赋给父结点
25+
array[parent] = array[child];
26+
27+
// 选取孩子结点的左孩子结点,继续向下筛选
28+
parent = child;
29+
child = 2 * child + 1;
30+
}
31+
32+
array[parent] = temp;
33+
}
34+
35+
@Override
36+
public void sort(int[] list) {
37+
// 循环建立初始堆
38+
for (int i = list.length / 2; i >= 0; i--) {
39+
heapadjust(list, i, list.length);
40+
}
41+
42+
// 进行n-1次循环，完成排序
43+
for (int i = list.length - 1; i > 0; i--) {
44+
// 最后一个元素和第一元素进行交换
45+
int temp = list[i];
46+
list[i] = list[0];
47+
list[0] = temp;
48+
49+
// 筛选 R[0] 结点，得到i-1个结点的堆
50+
heapadjust(list, 0, i);
51+
System.out.format("第 %d 趟: \n", list.length - i);
52+
ArrayUtil.printArray(list, 0, list.length - 1);
53+
}
54+
}
55+
}

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

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
package io.github.dunwu.algorithm.sort.strategy;
2+
3+
import io.github.dunwu.algorithm.sort.ArrayUtil;
4+
import io.github.dunwu.algorithm.sort.Sort;
5+
6+
public class InsertSort implements Sort {
7+
@Override
8+
public void sort(int[] list) {
9+
// 打印第一个元素
10+
System.out.format("i = %d:\t", 0);
11+
ArrayUtil.printArray(list, 0, 0);
12+
13+
// 第1个数肯定是有序的，从第2个数开始遍历，依次插入有序序列
14+
for (int i = 1; i < list.length; i++) {
15+
int j = 0;
16+
// 取出第i个数，和前i-1个数比较后，插入合适位置
17+
int temp = list[i];
18+
19+
// 因为前i-1个数都是从小到大的有序序列，所以只要当前比较的数(list[j])比temp大，就把这个数后移一位
20+
for (j = i - 1; j >= 0 && temp < list[j]; j--) {
21+
list[j + 1] = list[j];
22+
}
23+
list[j + 1] = temp;
24+
25+
System.out.format("i = %d:\t", i);
26+
ArrayUtil.printArray(list, 0, i);
27+
}
28+
}
29+
}

0 commit comments

Comments
 (0)