[A] 添加堆排序

coderbruis · coderbruis · commit fab524cc20fa · 2020-08-12T22:50:48.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
@@ -1,6 +1,13 @@
 package com.bruis.algorithminjava.algorithm.sort;
 
+import java.util.Random;
+
 /**
+ *
+ * 原地堆排序！ 不需要额外的空间
+ *
+ * 这里构造出来的是一个最小堆！！！！ 即数组的值依次递增
+ *
  * @author LuoHaiYang
  */
 public class HeapSort {
@@ -11,13 +18,22 @@ public static void sort(int[] arr) {
         // 注意，此时我们的堆是从0开始索引的
         // 从(最后一个元素的索引-1)/2开始
         // 最后一个元素的索引 = n-1
+        // 其实这里 i = (n-1) 也行
         for (int i = (n - 1 - 1) / 2; i >= 0; i--) {
-            shiftDown(arr, n, i);
+            siftDown2(arr, n, i);
+        }
+
+        // [a.....v,k]
+        // [.......]k
+        // [.....] ba
+        for (int i = n-1; i > 0; i--) {
+            swap(arr, 0, i);
+            siftDown2(arr, i, 0);
         }
     }
 
     // 下浮
-    public static void shiftDown(int[] arr, int n, int k) {
+    public static void siftDown(int[] arr, int n, int k) {
 
         while (2 * k + 1 < n) {
             int j = 2 * k + 1;
@@ -32,9 +48,59 @@ public static void shiftDown(int[] arr, int n, int k) {
         }
     }
 
+    /**
+     * 优化下沉过程, 不适用swap交换，通过赋值来代替。
+     *
+     * @param arr
+     * @param n
+     * @param k
+     */
+    private static void siftDown2(int[] arr, int n, int k) {
+
+        int e = arr[k];
+
+        while (2 * k + 1 < n) {
+            int j = 2 * k + 1;
+            if (j + 1 < n && arr[j + 1] > arr[j]) {
+                j++;
+            }
+
+            if (e >= arr[j]) {
+                break;
+            }
+            // 此时说明arr[j] > arr[k]; 所以让大值上浮;
+            arr[k] = arr[j];
+            k = j;
+        }
+        // 就是这一个替换，让此堆变成了最小堆;
+        // 这是因为while循环结束后，最小值以及替换到了arr[k]了，所以
+        arr[k] = e;
+    }
+
     public static void swap(int[] arr, int i, int j) {
         int tmp = arr[i];
         arr[i] = arr[j];
         arr[j] = tmp;
     }
+
+    public static void main(String[] args) {
+/*
+        int n = 100;
+        int[] test = new int[n];
+        Random random = new Random();
+        for (int i = 0; i < n; i++) {
+            test[i] = random.nextInt(1000);
+        }
+*/
+        int n = 10;
+        int[] test = {10, 41, 30, 28, 16, 22, 13, 19, 17, 15};
+
+        sort(test);
+
+        for (int i = 1; i < n; i++) {
+            if (test[i-1] > test[i]) {
+                throw new IllegalArgumentException("Error!");
+            }
+        }
+    }
 }
diff --git a/src/main/java/com/bruis/algorithminjava/datastructures/heap/MaxHeap.java b/src/main/java/com/bruis/algorithminjava/datastructures/heap/MaxHeap.java
@@ -46,6 +46,8 @@ public MaxHeap(int[] data) {
         size = n;
 
         // 这里需要注意，size / 2 得到的索引是二叉堆中最后一个非叶子节点。
+        // 注意！！！ 这里size / 2 是因为 data 从1开始的，所以最后一个非叶子节点为：size / 2
+        // 如果是从0开始，则：size - 1
         for (int i = size / 2; i > 0; i++) {
             siftDown(i);
         }

Original file line number	Diff line number	Diff line change
`@@ -46,6 +46,8 @@ public MaxHeap(int[] data) {`
`46`	`46`	`size = n;`
`47`	`47`
`48`	`48`	`// 这里需要注意，size / 2 得到的索引是二叉堆中最后一个非叶子节点。`
	`49`	`+ // 注意！！！这里size / 2 是因为 data 从1开始的，所以最后一个非叶子节点为：size / 2`
	`50`	`+ // 如果是从0开始，则：size - 1`
`49`	`51`	`for (int i = size / 2; i > 0; i++) {`
`50`	`52`	`siftDown(i);`
`51`	`53`	`}`