Skip to content

Commit 27e5f80

Browse files
author
chenweijie
committed
排序
1 parent 1f6974a commit 27e5f80

File tree

8 files changed

+98
-71
lines changed

8 files changed

+98
-71
lines changed

‎src/main/java/com/chen/algorithm/sort/BubbleSort2.java

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

‎src/main/java/com/chen/algorithm/sort/standrd/BubbleSort.java

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -14,10 +14,10 @@ public void bubbleSort1() {
1414

1515
int[] numbers = {1, 4, 7, 2, 10};
1616

17-
int size = numbers.length;
17+
int length = numbers.length;
1818
boolean flag = false;
19-
for (int i = 0; i < size; i++) {
20-
for (int j = 0; j < size - i; j++) {
19+
for (int i = 0; i < length; i++) {
20+
for (int j = 0; j < length - i - 1; j++) {
2121
if (numbers[j] > numbers[j + 1]) {
2222
int temp = numbers[j];
2323
numbers[j] = numbers[j + 1];

‎src/main/java/com/chen/algorithm/sort/test2/ChoiceSort.java

Lines changed: 26 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -2,6 +2,8 @@
22

33
import org.junit.Test;
44

5+
import java.util.Arrays;
6+
57
/**
68
* @author : chen weijie
79
* @Date: 2020-07-21 10:58
@@ -33,10 +35,31 @@ public void sort(int[] array) {
3335
@Test
3436
public void testCase() {
3537
int[] array = {4, 2, 1, 5, 10, -1};
36-
sort(array);
37-
for (int i = 0; i < array.length; i++) {
38-
System.out.println(array[i]);
38+
sort2(array);
39+
System.out.println(Arrays.toString(array));
40+
}
41+
42+
43+
public void sort2(int[] nums) {
44+
45+
46+
for (int i = 0; i < nums.length; i++) {
47+
int min = i;
48+
for (int j = i + 1; j < nums.length; j++) {
49+
if (nums[j] < nums[min]) {
50+
min = j;
51+
}
52+
}
53+
54+
if (min != i) {
55+
int tem = nums[min];
56+
nums[min] = nums[i];
57+
nums[i] = tem;
58+
}
59+
3960
}
61+
62+
4063
}
4164

4265

‎src/main/java/com/chen/algorithm/sort/test2/InsertSort.java

Lines changed: 22 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -2,6 +2,8 @@
22

33
import org.junit.Test;
44

5+
import java.util.Arrays;
6+
57
/**
68
* @author : chen weijie
79
* @Date: 2020-07-21 11:12
@@ -30,10 +32,27 @@ public void sort(int[] array) {
3032
@Test
3133
public void testCase() {
3234
int[] array = {4, 2, 1, 5, 10, -1};
33-
sort(array);
34-
for (int i = 0; i < array.length; i++) {
35-
System.out.println(array[i]);
35+
sort2(array);
36+
System.out.println(Arrays.toString(array));
37+
}
38+
39+
public void sort2(int[] nums) {
40+
41+
42+
for (int i = 1; i < nums.length; i++) {
43+
44+
int leftIndex = i - 1;
45+
int temp = nums[i];
46+
47+
while (leftIndex >= 0 && nums[leftIndex] > temp) {
48+
nums[leftIndex + 1] = nums[leftIndex];
49+
leftIndex--;
50+
}
51+
nums[leftIndex + 1] = temp;
52+
3653
}
54+
55+
3756
}
3857

3958

‎src/main/java/com/chen/algorithm/sort/test2/MergeSort.java

Lines changed: 36 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -45,10 +45,45 @@ public void mergeSort(int low, int high, int[] a) {
4545
}
4646
}
4747

48+
public void merge2(int left, int right, int mid, int[] nums) {
49+
50+
int i = left, j = mid + 1, k = 0;
51+
int[] temp = new int[right - left + 1];
52+
53+
while (i <= mid && j <= right) {
54+
if (nums[i] < nums[j]) {
55+
temp[k++] = nums[i++];
56+
} else {
57+
temp[k++] = nums[j++];
58+
}
59+
}
60+
61+
while (i <= mid) {
62+
temp[k++] = nums[i++];
63+
}
64+
65+
while (j <= right) {
66+
temp[k++] = nums[j++];
67+
}
68+
69+
System.arraycopy(temp, 0, nums, left, temp.length);
70+
}
71+
72+
73+
public void mergeSort2(int left, int right, int[] nums) {
74+
75+
if (right > left) {
76+
int mid = (left + right) / 2;
77+
mergeSort2(left, mid, nums);
78+
mergeSort2(mid + 1, right, nums);
79+
merge2(left, right, mid, nums);
80+
}
81+
}
82+
4883
@Test
4984
public void testCase() {
5085
int[] a = {4, 1, 3, 10, 13, 232, -1};
51-
mergeSort(0, a.length - 1, a);
86+
mergeSort2(0, a.length - 1, a);
5287
System.out.println("result=" + Arrays.toString(a));
5388
}
5489

‎src/main/java/com/chen/algorithm/study/test19/Solution2.java

Lines changed: 7 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -22,23 +22,22 @@ public ListNode getKthFromEnd(ListNode head, int k) {
2222
return null;
2323
}
2424

25-
ListNode temp = new ListNode(-1);
26-
temp.next = head;
27-
ListNode slow = head;
28-
ListNode fast = head;
25+
ListNode pre = new ListNode(-1);
26+
pre.next = head;
27+
ListNode slow = pre;
28+
ListNode fast = pre;
2929

30-
for (int i = 1; i <= k+1 ; i++) {
30+
for (int i = 0; i < k ; i++) {
3131
fast = fast.next;
3232
}
3333

34-
while (fast != null) {
34+
while (fast.next != null) {
3535
fast = fast.next;
3636
slow = slow.next;
3737
}
3838

3939
slow.next = slow.next.next;
40-
41-
return temp.next;
40+
return pre.next;
4241
}
4342

4443
}

‎src/main/java/com/chen/algorithm/study/test714/Solution.java

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -15,7 +15,7 @@ public int maxProfit(int[] prices, int fee) {
1515
return 0;
1616
}
1717

18-
// dp[i][j] 表示 [0, i] 区间内，到第 i 天（从 0 开始）状态为 j 时的最大收益'
18+
// dp[i][j] 表示 [0, i] 区间内，到第 i 天（从 0 开始）状态为 j 时的最大收益
1919
// j = 0 表示不持股，j = 1 表示持股
2020
// 并且规定在买入股票的时候，扣除手续费
2121
int[][] dp = new int[len][2];

‎src/main/java/com/chen/algorithm/study/test72/Solution.java

Lines changed: 3 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -20,13 +20,15 @@ public int minDistance(String word1, String word2) {
2020
return m + n;
2121
}
2222

23-
//TODO 为什么要设置为+1；
23+
// 多开一行一列是为了保存边界条件，即字符长度为 0 的情况，这一点在字符串的动态规划问题中比较常见
2424
int[][] dp = new int[m + 1][n + 1];
2525

26+
// 初始化：当 word 2 长度为 0 时，将 word1 的全部删除
2627
for (int i = 0; i < m + 1; i++) {
2728
dp[i][0] = i;
2829
}
2930

31+
// 当 word1 长度为 0 时，就插入所有 word2 的字符
3032
for (int j = 0; j < n + 1; j++) {
3133
dp[0][j] = j;
3234
}

0 commit comments

Comments
 (0)