修改插入排序错误

Yuhuiyang-Dev · Yuhuiyang-Dev · commit af09b91f37cc · 2019-03-10T21:23:02.000+08:00
diff --git a/「一入 Java 深似海 」/代码/segmentfault/deep-in-java/stage-2/lesson-4/src/main/java/com/segmentfault/deep/in/java/collection/algorithm/BubbleSort.java b/「一入 Java 深似海 」/代码/segmentfault/deep-in-java/stage-2/lesson-4/src/main/java/com/segmentfault/deep/in/java/collection/algorithm/BubbleSort.java
@@ -39,13 +39,13 @@ public static void main(String[] args) {
         Integer[] values = Sort.of(3, 1, 2, 5, 4);
         Sort<Integer> sort = new BubbleSort<>(); // Java 7 Diamond 语法
         sort.sort(values);
-        System.out.printf("排序结果：%s", Arrays.toString(values));
+        System.out.printf("排序结果：%s\n", Arrays.toString(values));
 
         System.out.println("完全逆序");
         values = Sort.of(5, 4, 3, 2, 1);
         sort = new BubbleSort<>();
         sort.sort(values);
-        System.out.printf("排序结果：%s", Arrays.toString(values));
+        System.out.printf("排序结果：%s\n", Arrays.toString(values));
     }
 
 }
diff --git a/「一入 Java 深似海 」/代码/segmentfault/deep-in-java/stage-2/lesson-4/src/main/java/com/segmentfault/deep/in/java/collection/algorithm/InsertionSort.java b/「一入 Java 深似海 」/代码/segmentfault/deep-in-java/stage-2/lesson-4/src/main/java/com/segmentfault/deep/in/java/collection/algorithm/InsertionSort.java
@@ -1,6 +1,6 @@
 package com.segmentfault.deep.in.java.collection.algorithm;
 
-import java.util.stream.Stream;
+import java.util.Arrays;
 
 public class InsertionSort<T extends Comparable<T>> implements Sort<T> {
 
@@ -17,20 +17,30 @@ public void sort(T[] values) {
             // [j = 0] = 3, [i = 1] = 1 , t = [i = 1] = 1
             // [i = 1] = [j = 0] , [j = 0] = t = 1
             T t = values[i]; // 产生临时变量
-            for (int j = i - 1; j >= 0; j--) {
-                if (t.compareTo(values[j]) < 1) { // 高位 < 低位
-                    values[i] = values[j]; // 高位获取低位的值
-                    values[j] = t; // 低位得到高位的值
-                }
+            int j = i;
+            while (j > 0 && t.compareTo(values[j - 1]) < 0) {
+                //往后移动让出插入空间
+                values[j] = values[j - 1];
+                j--;
             }
+            //插入values[i]到对应位置
+            values[j] = t;
+            System.out.printf("第%d轮：%s\n", i, Arrays.toString(values));
         }
     }
 
     public static void main(String[] args) {
-        Integer[] values = Sort.of(3, 1, 2, 5, 4);
-        Sort<Integer> sort = new InsertionSort<>(); // Java 7 Diamond 语法
+        System.out.println("一般情况");
+        Integer[] values = Sort.of(3, 2, 1, 5, 4);
+        Sort<Integer> sort = new InsertionSort<>();
         sort.sort(values);
-        Stream.of(values).forEach(System.out::println);
+        System.out.println(Arrays.toString(values));
+
+        System.out.println("完全逆序");
+        values = Sort.of(5, 4, 3, 2, 1);
+        sort = new InsertionSort<>();
+        sort.sort(values);
+        System.out.println(Arrays.toString(values));
     }
 
 }

Original file line number	Diff line number	Diff line change
`@@ -39,13 +39,13 @@ public static void main(String[] args) {`
`39`	`39`	`Integer[] values = Sort.of(3, 1, 2, 5, 4);`
`40`	`40`	`Sort<Integer> sort = new BubbleSort<>(); // Java 7 Diamond 语法`
`41`	`41`	`sort.sort(values);`
`42`		`- System.out.printf("排序结果：%s", Arrays.toString(values));`
	`42`	`+ System.out.printf("排序结果：%s\n", Arrays.toString(values));`
`43`	`43`
`44`	`44`	`System.out.println("完全逆序");`
`45`	`45`	`values = Sort.of(5, 4, 3, 2, 1);`
`46`	`46`	`sort = new BubbleSort<>();`
`47`	`47`	`sort.sort(values);`
`48`		`- System.out.printf("排序结果：%s", Arrays.toString(values));`
	`48`	`+ System.out.printf("排序结果：%s\n", Arrays.toString(values));`
`49`	`49`	`}`
`50`	`50`
`51`	`51`	`}`