[U] 更新堆排序实现

coderbruis · coderbruis · commit ece145ebdb4d · 2020-08-13T09:27:35.000+08:00
diff --git a/src/main/java/com/bruis/algorithminjava/algorithm/sort/HeapSort.java b/src/main/java/com/bruis/algorithminjava/algorithm/sort/HeapSort.java
@@ -27,7 +27,9 @@ public static void sort(int[] arr) {
         // [.......]k
         // [.....] ba
         for (int i = n-1; i > 0; i--) {
+            // 由于上面执行过下沉操作，所以已经是最大堆（但没有排序完）。所以此时swap就将最大值替换到数组末尾。
             swap(arr, 0, i);
+            // 由于siftDown中是判断 2*k+1 < n ，所以就是对n-1进行下沉操作；
             siftDown2(arr, i, 0);
         }
     }
@@ -72,8 +74,7 @@ private static void siftDown2(int[] arr, int n, int k) {
             arr[k] = arr[j];
             k = j;
         }
-        // 就是这一个替换，让此堆变成了最小堆;
-        // 这是因为while循环结束后，最小值以及替换到了arr[k]了，所以
+        // 将最小元素替换到k的位置
         arr[k] = e;
     }
 

Original file line number	Diff line number	Diff line change
`@@ -27,7 +27,9 @@ public static void sort(int[] arr) {`
`27`	`27`	`// [.......]k`
`28`	`28`	`// [.....] ba`
`29`	`29`	`for (int i = n-1; i > 0; i--) {`
	`30`	`+ // 由于上面执行过下沉操作，所以已经是最大堆（但没有排序完）。所以此时swap就将最大值替换到数组末尾。`
`30`	`31`	`swap(arr, 0, i);`
	`32`	`+ // 由于siftDown中是判断 2*k+1 < n ，所以就是对n-1进行下沉操作；`
`31`	`33`	`siftDown2(arr, i, 0);`
`32`	`34`	`}`
`33`	`35`	`}`
`@@ -72,8 +74,7 @@ private static void siftDown2(int[] arr, int n, int k) {`
`72`	`74`	`arr[k] = arr[j];`
`73`	`75`	`k = j;`
`74`	`76`	`}`
`75`		`- // 就是这一个替换，让此堆变成了最小堆;`
`76`		`- // 这是因为while循环结束后，最小值以及替换到了arr[k]了，所以`
	`77`	`+ // 将最小元素替换到k的位置`
`77`	`78`	`arr[k] = e;`
`78`	`79`	`}`
`79`	`80`