?
?
1. 堆排序原理圖解
?
堆排序是一種基于二叉堆（通常使用最大堆）的排序算法。其核心思想是利用堆的性質（父節點的值大于或等于子節點的值）來高效地進行排序。堆排序分為兩個主要階段：建堆和排序。
?
堆排序步驟：
?
1. 建堆：
? ?- 將無序數組構建成一個最大堆。
? ?- 從最后一個非葉子節點開始，逐個調整節點，使其滿足堆的性質。
?
2. 排序：
? ?- 將堆頂元素（最大值）與堆的最后一個元素交換。
? ?- 縮小堆的范圍，重新調整堆，使其滿足最大堆的性質。
? ?- 重復上述過程，直到堆的大小為1。
?
圖解示例：
?
假設數組為 `[4, 10, 3, 5, 1]`。
?
1. 初始狀態：`[4, 10, 3, 5, 1]`
2. 建堆：
? ?- 調整節點，構建最大堆：`[10, 5, 3, 4, 1]`
3. 排序過程：
? ?- 將堆頂元素（10）與最后一個元素（1）交換：`[1, 5, 3, 4, 10]`
? ?- 調整剩余的堆（`[1, 5, 3, 4]`），使其滿足最大堆的性質：`[5, 4, 3, 1]`
? ?- 將堆頂元素（5）與最后一個元素（1）交換：`[1, 4, 3, 5, 10]`
? ?- 調整剩余的堆（`[1, 4, 3]`），使其滿足最大堆的性質：`[4, 1, 3]`
? ?- 將堆頂元素（4）與最后一個元素（3）交換：`[3, 1, 4, 5, 10]`
? ?- 調整剩余的堆（`[3, 1]`），使其滿足最大堆的性質：`[3, 1]`
? ?- 將堆頂元素（3）與最后一個元素（1）交換：`[1, 3, 4, 5, 10]`
4. **最終結果**：`[1, 3, 4, 5, 10]`
?
?2. Java代碼實現及注釋
?
```java
import java.util.Arrays;
?
public class HeapSort {
? ? public static void main(String[] args) {
? ? ? ? int[] array = {4, 10, 3, 5, 1};
? ? ? ? heapSort(array);
? ? ? ? System.out.println("排序后的數組：");
? ? ? ? System.out.println(Arrays.toString(array));
? ? }
?
? ? // 堆排序主方法
? ? public static void heapSort(int[] arr) {
? ? ? ? int n = arr.length;
?
? ? ? ? // 建堆：從最后一個非葉子節點開始，逐個調整節點
? ? ? ? for (int i = n / 2 - 1; i >= 0; i--) {
? ? ? ? ? ? heapify(arr, n, i);
? ? ? ? }
?
? ? ? ? // 排序：交換堆頂元素與最后一個元素，然后調整堆
? ? ? ? for (int i = n - 1; i >= 0; i--) {
? ? ? ? ? ? // 交換堆頂元素與最后一個元素
? ? ? ? ? ? int temp = arr[0];
? ? ? ? ? ? arr[0] = arr[i];
? ? ? ? ? ? arr[i] = temp;
?
? ? ? ? ? ? // 調整剩余的堆
? ? ? ? ? ? heapify(arr, i, 0);
? ? ? ? }
? ? }
?
? ? // 調整堆的方法
? ? private static void heapify(int[] arr, int heapSize, int rootIndex) {
? ? ? ? int largest = rootIndex; // 假設根節點是最大的
? ? ? ? int leftChild = 2 * rootIndex + 1; // 左子節點
? ? ? ? int rightChild = 2 * rootIndex + 2; // 右子節點
?
? ? ? ? // 如果左子節點大于根節點
? ? ? ? if (leftChild < heapSize && arr[leftChild] > arr[largest]) {
? ? ? ? ? ? largest = leftChild;
? ? ? ? }
?
? ? ? ? // 如果右子節點大于當前最大的節點
? ? ? ? if (rightChild < heapSize && arr[rightChild] > arr[largest]) {
? ? ? ? ? ? largest = rightChild;
? ? ? ? }
?
? ? ? ? // 如果最大的節點不是根節點，交換它們
? ? ? ? if (largest != rootIndex) {
? ? ? ? ? ? int temp = arr[rootIndex];
? ? ? ? ? ? arr[rootIndex] = arr[largest];
? ? ? ? ? ? arr[largest] = temp;
?
? ? ? ? ? ? // 遞歸調整子樹
? ? ? ? ? ? heapify(arr, heapSize, largest);
? ? ? ? }
? ? }
}
```
?
?3. 代碼說明
?
1. 建堆：
? ?- 從最后一個非葉子節點開始，逐個調整節點，使其滿足最大堆的性質。
? ?- 使用 `heapify` 方法調整節點。
?
2. 排序：
? ?- 將堆頂元素（最大值）與堆的最后一個元素交換。
? ?- 縮小堆的范圍，重新調整堆，使其滿足最大堆的性質。
? ?- 重復上述過程，直到堆的大小為1。
?
3. 時間復雜度：
? ?- **最壞情況**：`O(n log n)`。
? ?- **平均情況**：`O(n log n)`。
? ?- **最好情況**：`O(n log n)`。
?
4. 空間復雜度：
? ?- `O(1)`，因為堆排序是原地排序算法，不需要額外的存儲空間。
?
5. 穩定性：
? ?- 堆排序是**不穩定的**，因為交換操作可能改變相同值元素的相對順序。
?
4. 應用場景
?
1. 大規模數據排序：
? ?- 堆排序的時間復雜度為 `O(n log n)`，適合對大規模數據進行排序。
?
2. 優先隊列實現：
? ?- 堆排序的核心思想可以用于實現優先隊列，例如在任務調度中。
?
3. 教學和演示：
? ?- 堆排序的實現清晰，適合用于教學和算法演示。
?
?5. 總結
?
堆排序是一種高效的排序算法，基于二叉堆的性質實現。它的時間復雜度穩定在 `O(n log n)`，并且是原地排序算法，不需要額外的存儲空間。然而，堆排序是不穩定的，因此在需要保持相同值元素相對順序的場景中不適用。在實際應用中，堆排序常用于大規模數據排序和優先隊列的實現。
)
：自動切換回主線程；bulid的過程；create方法+ServiceMethod源碼了解)
)