Skip to content

Commit 5141d08

Browse files
yanglbmeyanglbme
committed
feat: update common sorting algorithms
更新常见的排序算法
1 parent efd397c commit 5141d08

4 files changed

Lines changed: 47 additions & 37 deletions

File tree

‎basic/README.md‎

Lines changed: 5 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -4,4 +4,8 @@
44

55
- 冒泡排序
66
- 插入排序
7-
- 归并排序
7+
- 归并排序
8+
- 快速排序
9+
- 拓扑排序
10+
- 堆排序
11+
- 桶排序

‎basic/sort/BubbleSort.java‎

Lines changed: 9 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -1,17 +1,12 @@
11
import java.util.Arrays;
22

33
public class BubbleSort {
4-
private static void swap(int[] nums, int i, int j) {
5-
int t = nums[i];
6-
nums[i] = nums[j];
7-
nums[j] = t;
8-
}
94

105
private static void bubbleSort(int[] nums) {
116
boolean hasChange = true;
12-
for (int i = 0; i < nums.length - 1 && hasChange; ++i) {
7+
for (int i = 0, n = nums.length; i < n - 1 && hasChange; ++i) {
138
hasChange = false;
14-
for (int j = 0; j < nums.length - 1 - i; ++j) {
9+
for (int j = 0; j < n - i - 1; ++j) {
1510
if (nums[j] > nums[j + 1]) {
1611
swap(nums, j, j + 1);
1712
hasChange = true;
@@ -20,9 +15,15 @@ private static void bubbleSort(int[] nums) {
2015
}
2116
}
2217

18+
private static void swap(int[] nums, int i, int j) {
19+
int t = nums[i];
20+
nums[i] = nums[j];
21+
nums[j] = t;
22+
}
23+
2324
public static void main(String[] args) {
2425
int[] nums = {1, 2, 7, 9, 5, 8};
2526
bubbleSort(nums);
2627
System.out.println(Arrays.toString(nums));
2728
}
28-
}
29+
}

‎basic/sort/InsertionSort.java‎

Lines changed: 8 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -1,19 +1,20 @@
11
import java.util.Arrays;
22

33
public class InsertionSort {
4+
45
private static void insertionSort(int[] nums) {
5-
for (int i = 1, j, current; i < nums.length; ++i) {
6-
current = nums[i];
7-
for (j = i - 1; j >= 0 && nums[j] > current; --j) {
6+
for (int i = 1, j, n = nums.length; i < n; ++i) {
7+
int num = nums[i];
8+
for (j = i - 1; j >=0 && nums[j] > num; --j) {
89
nums[j + 1] = nums[j];
910
}
10-
nums[j + 1] = current;
11+
nums[j + 1] = num;
1112
}
1213
}
13-
14+
1415
public static void main(String[] args) {
15-
int[] nums = { 1, 2, 7, 9, 5, 8 };
16+
int[] nums = {1, 2, 7, 9, 5, 8};
1617
insertionSort(nums);
1718
System.out.println(Arrays.toString(nums));
1819
}
19-
}
20+
}

‎basic/sort/README.md‎

Lines changed: 25 additions & 21 deletions
Original file line numberDiff line numberDiff line change
@@ -4,23 +4,20 @@
44

55
定义一个布尔变量 `hasChange`，用来标记每轮是否进行了交换。在每轮遍历开始时，将 `hasChange` 设置为 false。
66

7+
若当轮没有发生交换，说明此时数组已经按照升序排列，`hashChange` 依然是为 false。此时外层循环直接退出，排序结束。
8+
79
### 代码示例
810

911
```java
1012
import java.util.Arrays;
1113

1214
public class BubbleSort {
13-
private static void swap(int[] nums, int i, int j) {
14-
int t = nums[i];
15-
nums[i] = nums[j];
16-
nums[j] = t;
17-
}
1815

1916
private static void bubbleSort(int[] nums) {
2017
boolean hasChange = true;
21-
for (int i = 0; i < nums.length - 1 && hasChange; ++i) {
18+
for (int i = 0, n = nums.length; i < n - 1 && hasChange; ++i) {
2219
hasChange = false;
23-
for (int j = 0; j < nums.length - 1 - i; ++j) {
20+
for (int j = 0; j < n - i - 1; ++j) {
2421
if (nums[j] > nums[j + 1]) {
2522
swap(nums, j, j + 1);
2623
hasChange = true;
@@ -29,6 +26,12 @@ public class BubbleSort {
2926
}
3027
}
3128

29+
private static void swap(int[] nums, int i, int j) {
30+
int t = nums[i];
31+
nums[i] = nums[j];
32+
nums[j] = t;
33+
}
34+
3235
public static void main(String[] args) {
3336
int[] nums = {1, 2, 7, 9, 5, 8};
3437
bubbleSort(nums);
@@ -39,15 +42,15 @@ public class BubbleSort {
3942

4043
### 算法分析
4144

42-
空间复杂度 O(1)、时间复杂度 O(n^2)。
45+
空间复杂度 O(1)、时间复杂度 O(n²)。
4346

4447
分情况讨论：
4548

4649
1. 给定的数组按照顺序已经排好：只需要进行 `n-1` 次比较，两两交换次数为 0，时间复杂度为 O(n)，这是最好的情况。
47-
2. 给定的数组按照逆序排列：需要进行 `n*(n-1)/2` 次比较，时间复杂度为 O(n^2)，这是最坏的情况。
48-
3. 给定的数组杂乱无章。在这种情况下，平均时间复杂度 O(n^2)。
50+
2. 给定的数组按照逆序排列：需要进行 `n*(n-1)/2` 次比较，时间复杂度为 O(n²)，这是最坏的情况。
51+
3. 给定的数组杂乱无章。在这种情况下，平均时间复杂度 O(n²)。
4952

50-
因此，时间复杂度是 O(n^2)，这是一种稳定的排序算法。
53+
因此，时间复杂度是 O(n²)，这是一种稳定的排序算法。
5154

5255
> 稳定是指，两个相等的数，在排序过后，相对位置保持不变。
5356
@@ -66,18 +69,19 @@ public class BubbleSort {
6669
import java.util.Arrays;
6770

6871
public class InsertionSort {
72+
6973
private static void insertionSort(int[] nums) {
70-
for (int i = 1, j, current; i < nums.length; ++i) {
71-
current = nums[i];
72-
for (j = i - 1; j >= 0 && nums[j] > current; --j) {
74+
for (int i = 1, j, n = nums.length; i < n; ++i) {
75+
int num = nums[i];
76+
for (j = i - 1; j >=0 && nums[j] > num; --j) {
7377
nums[j + 1] = nums[j];
7478
}
75-
nums[j + 1] = current;
79+
nums[j + 1] = num;
7680
}
7781
}
78-
82+
7983
public static void main(String[] args) {
80-
int[] nums = { 1, 2, 7, 9, 5, 8 };
84+
int[] nums = {1, 2, 7, 9, 5, 8};
8185
insertionSort(nums);
8286
System.out.println(Arrays.toString(nums));
8387
}
@@ -86,15 +90,15 @@ public class InsertionSort {
8690

8791
### 算法分析
8892

89-
空间复杂度 O(1)，时间复杂度 O(n^2)。
93+
空间复杂度 O(1)，时间复杂度 O(n²)。
9094

9195
分情况讨论：
9296

9397
1. 给定的数组按照顺序排好序：只需要进行 n-1 次比较，两两交换次数为 0，时间复杂度为 O(n)，这是最好的情况。
94-
2. 给定的数组按照逆序排列：需要进行 `n*(n-1)/2` 次比较，时间复杂度为 O(n^2)，这是最坏的情况。
95-
3. 给定的数组杂乱无章：在这种情况下，平均时间复杂度是 O(n^2)。
98+
2. 给定的数组按照逆序排列：需要进行 `n*(n-1)/2` 次比较，时间复杂度为 O(n²)，这是最坏的情况。
99+
3. 给定的数组杂乱无章：在这种情况下，平均时间复杂度是 O(n²)。
96100

97-
因此，时间复杂度是 O(n^2)，这也是一种稳定的排序算法。
101+
因此，时间复杂度是 O(n²)，这也是一种稳定的排序算法。
98102

99103
## 归并排序
100104

0 commit comments

Comments
 (0)