? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

??????🌈個人主頁：人不走空??????

💖系列專欄：算法專題

?詩詞歌賦：斯是陋室，惟吾德馨

目錄

??????🌈個人主頁：人不走空??????

💖系列專欄：算法專題

?詩詞歌賦：斯是陋室，惟吾德馨

堆排序的基本思想

堆排序的步驟

代碼示例（Java）

代碼解釋

運行結果

堆排序的特點

總結

作者其他作品：

---

?

堆排序（Heap Sort）是一種基于堆數據結構的比較排序算法。堆是一棵完全二叉樹，具有堆屬性：對于最大堆，每個節點的值都大于或等于其子節點的值；對于最小堆，每個節點的值都小于或等于其子節點的值。堆排序利用了堆的這一特性來實現高效的排序。

堆排序的基本思想

堆排序的基本思想是先將待排序的數組構造成一個最大堆（或最小堆），然后通過不斷地取出堆頂元素（最大值或最小值），重建堆，從而完成排序。

堆排序的步驟

1. 構建最大堆：

   • 從數組的中間開始（即最后一個非葉子節點），向前遍歷，將每個節點和其子節點重新排列，使得整個數組符合最大堆的特性。

2. 排序：

   • 將堆頂元素（最大值）與數組末尾元素交換，這樣最大值就放到了最終的位置。
   • 將數組長度減 1（排除已經放置到最終位置的元素），重新調整堆，使其再次滿足最大堆的特性。
   • 重復上述步驟，直到整個數組有序。

代碼示例（Java）

public class HeapSort {public static void heapSort(int[] array) {int n = array.length;// 構建最大堆for (int i = n / 2 - 1; i >= 0; i--) {heapify(array, n, i);}// 一個一個從堆頂取出元素，放到已排序區域for (int i = n - 1; i > 0; i--) {// 交換當前堆頂元素和當前未排序部分的最后一個元素swap(array, 0, i);// 調整剩下的堆，長度減 1heapify(array, i, 0);}}private static void heapify(int[] array, int n, int i) {int largest = i;        // 假設當前節點 i 是最大值int left = 2 * i + 1;   // 左子節點索引int right = 2 * i + 2;  // 右子節點索引// 如果左子節點存在且大于當前節點，則更新 largestif (left < n && array[left] > array[largest]) {largest = left;}// 如果右子節點存在且大于當前節點，則更新 largestif (right < n && array[right] > array[largest]) {largest = right;}// 如果 largest 不是當前節點 i，交換它們并繼續調整if (largest != i) {swap(array, i, largest);heapify(array, n, largest);}}private static void swap(int[] array, int i, int j) {int temp = array[i];array[i] = array[j];array[j] = temp;}public static void main(String[] args) {int[] array = {12, 11, 13, 5, 6, 7};System.out.println("Original array: ");printArray(array);heapSort(array);System.out.println("Sorted array: ");printArray(array);}private static void printArray(int[] array) {for (int value : array) {System.out.print(value + " ");}System.out.println();}
}

代碼解釋

1. heapSort 方法：這是堆排序的主方法。首先，通過 heapify 函數構建最大堆，然后不斷將堆頂元素移到數組末尾，調整剩余的堆。

2. heapify 方法：調整以 i 為根的子樹，使其成為最大堆。它檢查 i 節點和其子節點的值，確保最大的值在 i 位置。如果 i 位置不是最大值，交換它和最大子節點的位置，并遞歸調整交換后的子樹。

3. swap 方法：交換數組中兩個元素的位置。

4. main 方法：演示如何使用 heapSort 方法排序一個整數數組，并打印排序前后的數組。

5. printArray 方法：用于打印數組元素。

運行結果

Original array: 
12 11 13 5 6 7 
Sorted array: 
5 6 7 11 12 13 

堆排序的特點

• 時間復雜度：堆排序在最壞、平均和最好情況下的時間復雜度均為 O(nlog?n)O(n \log n)O(nlogn)。
• 空間復雜度：堆排序的空間復雜度為 O(1)O(1)O(1)，因為它只需要常量級的額外空間。
• 穩定性：堆排序不是穩定的排序算法，因為在排序過程中，元素的相對順序可能會改變。

總結

堆排序是一種高效的排序算法，尤其適用于大數據量的排序。它利用堆這種數據結構的特點，保證了較好的時間復雜度和低空間消耗。雖然它不如快速排序常用，但在需要穩定的性能和低空間開銷時，堆排序是一個不錯的選擇。

---

作者其他作品：

【Java】Spring循環依賴：原因與解決方法

OpenAI Sora來了，視頻生成領域的GPT-4時代來了

[Java·算法·簡單] LeetCode 14. 最長公共前綴 詳細解讀

【Java】深入理解Java中的static關鍵字

[Java·算法·簡單] LeetCode 28. 找出字a符串中第一個匹配項的下標 詳細解讀

了解 Java 中的 AtomicInteger 類

算法題 — 整數轉二進制，查找其中1的數量

深入理解MySQL事務特性：保證數據完整性與一致性

Java企業應用軟件系統架構演變史?