Skip to content

Commit fae08d9

Browse files
NinaWanNinaWan
committed
Add details for bubble sort
1 parent 9c0cdcd commit fae08d9

File tree

7 files changed

+133
-17
lines changed

7 files changed

+133
-17
lines changed

‎.gitignore‎

100644100755
Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1 +1,2 @@
1-
.idea
1+
.idea
2+
/target/

‎pom.xml‎

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
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+
<groupId>groupId</groupId>
8+
<artifactId>Algorithm</artifactId>
9+
<version>1.0-SNAPSHOT</version>
10+
<dependencies>
11+
<dependency>
12+
<groupId>org.junit.jupiter</groupId>
13+
<artifactId>junit-jupiter</artifactId>
14+
<version>5.8.2</version>
15+
<scope>test</scope>
16+
</dependency>
17+
</dependencies>
18+
19+
<properties>
20+
<maven.compiler.source>8</maven.compiler.source>
21+
<maven.compiler.target>8</maven.compiler.target>
22+
</properties>
23+
24+
</project>

‎sort/BubbleSort.java‎

Lines changed: 0 additions & 16 deletions
This file was deleted.

‎src/main/java/sort/bubble/BubbleSort.java‎

Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
package sort.bubble;
2+
3+
public class BubbleSort {
4+
public void sort_1(int[] nums) {
5+
int n = nums.length;
6+
7+
for (int i = n - 1; i >= 0; i--) {
8+
for (int j = 0; j < i; j++) {
9+
if (nums[j] > nums[j + 1]) {
10+
swap(nums, j, j + 1);
11+
}
12+
}
13+
}
14+
}
15+
16+
public void sort_2(int[] nums) {
17+
int n = nums.length;
18+
19+
for (int i = n - 1; i >= 0; i--) {
20+
boolean sorted = true;
21+
22+
for (int j = 0; j < i; j++) {
23+
if (nums[j] > nums[j + 1]) {
24+
swap(nums, j, j + 1);
25+
sorted = false;
26+
}
27+
}
28+
29+
if (sorted) {
30+
break;
31+
}
32+
}
33+
}
34+
35+
private void swap(int[] nums, int i, int j) {
36+
int tmp = nums[i];
37+
nums[i] = nums[j];
38+
nums[j] = tmp;
39+
}
40+
}

‎src/main/java/sort/bubble/bubble_sort.md‎

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
# Bubble Sort 冒泡排序
2+
3+
## 算法思想
4+
5+
每次比较相邻两项元素的大小，不符合预想顺序则交换。
6+
7+
## 实现方法
8+
9+
双重for循环
10+
11+
## 复杂度分析
12+
13+
### 前提
14+
15+
* 数组长度为n
16+
17+
### 时间复杂度
18+
19+
外循环遍历数组需要n时间，内循环遍历数组需要n时间
20+
21+
最优时间复杂度：数组已有序
22+
23+
平均时间复杂度：O(n<sup>2</sup>)
24+
25+
最差时间复杂度：数组逆序有序
26+
27+
### 空间复杂度
28+
29+
在原数组上操作，空间复杂度为O(1)
30+
31+
## 扩展/优化

‎src/test/java/sort/SortTest.java‎

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,6 @@
1+
package sort;
2+
3+
public class SortTest {
4+
protected int[] tested = {3, 2, 1};
5+
protected int[] expected = {1, 2, 3};
6+
}

‎src/test/java/sort/bubble/BubbleSortTest.java‎

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
package sort.bubble;
2+
3+
import org.junit.jupiter.api.BeforeEach;
4+
import org.junit.jupiter.api.Test;
5+
import sort.SortTest;
6+
7+
import static org.junit.jupiter.api.Assertions.assertArrayEquals;
8+
9+
class BubbleSortTest extends SortTest {
10+
private BubbleSort bubbleSort;
11+
12+
@BeforeEach
13+
public void setup() {
14+
bubbleSort = new BubbleSort();
15+
tested = new int[]{3, 2, 1};
16+
expected = new int[]{1, 2, 3};
17+
}
18+
19+
@Test
20+
void testSort1() {
21+
bubbleSort.sort_1(tested);
22+
assertArrayEquals(tested, expected);
23+
}
24+
25+
@Test
26+
void testSort2() {
27+
bubbleSort.sort_2(tested);
28+
assertArrayEquals(tested, expected);
29+
}
30+
}

0 commit comments

Comments
 (0)