目錄
?
優化堆排序
Java 實例代碼
src/runoob/heap/HeapSort.java 文件代碼：
?
優化堆排序
上一節的堆排序，我們開辟了額外的空間進行構造堆和對堆進行排序。這一小節，我們進行優化，使用原地堆排序。
對于一個最大堆，首先將開始位置數據和數組末尾數值進行交換，那么數組末尾就是最大元素，然后再對W元素進行 shift down 操作，重新生成最大堆，然后將新生成的最大數和整個數組倒數第二位置進行交換，此時倒數第二位置就是倒數第二大數據，這個過程以此類推。
整個過程可以用如下圖表示：
?
Java 實例代碼
源碼包下載：Download
https://www.runoob.com/wp-content/uploads/2020/09/runoob-algorithm-HeapSort.zip
src/runoob/heap/HeapSort.java 文件代碼：
package runoob.heap;
import runoob.sort.SortTestHelper;
/**
?* 原地堆排序
?*/
public class HeapSort<T extends Comparable> {
? ? public static void sort(Comparable[] arr) {
? ? ? ? int n = arr.length;
? ? ? ? // 注意，此時我們的堆是從0開始索引的
? ? ? ? // 從(最后一個元素的索引-1)/2開始
? ? ? ? // 最后一個元素的索引 = n-1
? ? ? ? for (int i = (n - 1 - 1) / 2; i >= 0; i--)
? ? ? ? ? ? shiftDown(arr, n, i);
? ? ? ?
? ? ? ? for (int i = n - 1; i > 0; i--) {
? ? ? ? ? ? swap(arr, 0, i);
? ? ? ? ? ? shiftDown(arr, i, 0);
? ? ? ? }
? ? }
? ? // 交換堆中索引為i和j的兩個元素
? ? private static void swap(Object[] arr, int i, int j) {
? ? ? ? Object t = arr[i];
? ? ? ? arr[i] = arr[j];
? ? ? ? arr[j] = t;
? ? }
? ? // 原始的shiftDown過程
? ? private static void shiftDown(Comparable[] arr, int n, int k) {
? ? ? ? while (2 * k + 1 < n) {
? ? ? ? ? ? //左孩子節點
? ? ? ? ? ? int j = 2 * k + 1;
? ? ? ? ? ? //右孩子節點比左孩子節點大
? ? ? ? ? ? if (j + 1 < n && arr[j + 1].compareTo(arr[j]) > 0)
? ? ? ? ? ? ? ? j += 1;
? ? ? ? ? ? //比兩孩子節點都大
? ? ? ? ? ? if (arr[k].compareTo(arr[j]) >= 0) break;
? ? ? ? ? ? //交換原節點和孩子節點的值
? ? ? ? ? ? swap(arr, k, j);
? ? ? ? ? ? k = j;
? ? ? ? }
? ? }
? ? // 測試 HeapSort
? ? public static void main(String[] args) {
? ? ? ? int N = 100;
? ? ? ? Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000);
? ? ? ? sort(arr);
? ? ? ? // 將heapify中的數據逐漸使用extractMax取出來
? ? ? ? // 取出來的順序應該是按照從大到小的順序取出來的
? ? ? ? for (int i = 0; i < N; i++) {
? ? ? ? ? ? System.out.print(arr[i] + " ");
? ? ? ? }
? ? ? ? // 確保arr數組是從大到小排列的
? ? ? ? for (int i = 1; i < N; i++)
? ? ? ? ? ? assert arr[i - 1] >= arr[i];
? ? }
}
?
?
)
)