堆排序：堆排序如何實現？時間複雜度詳解
堆排序是利用“堆”（特殊完全二叉樹）實現的排序算法，常用大頂堆（父節點≥子節點）。核心思想是“先建堆，再排序”：先將數組轉爲大頂堆（堆頂爲最大值），再反覆交換堆頂與末尾元素，調整剩餘元素爲堆，完成排序。 堆的基本概念：完全二叉樹結構，數組中索引i的左子節點2i+1、右子節點2i+2、父節點(i-1)//2。大頂堆父≥子，小頂堆父≤子。 實現分兩步：1.構建大頂堆：從最後非葉子節點開始，通過“堆化”（比較父與子節點，交換最大值並遞歸調整子樹）確保大頂堆性質；2.排序：交換堆頂與未排序末尾元素，縮小堆規模後重復堆化，直至完成。 時間複雜度：構建堆O(n)，排序過程O(n log n)，總O(n log n)，空間複雜度O(1)（原地排序）。特點是不穩定，適合大規模數據排序。
閱讀全文使用C++實現堆排序算法
堆排序是基於堆數據結構的高效排序算法，時間複雜度O(n log n)，空間複雜度O(1)，適用於大規模數據。堆是特殊完全二叉樹，分大頂堆（父≥子）和小頂堆，排序常用大頂堆。其存儲爲數組，索引i的父節點爲(i-1)/2，左右子節點爲2i+1和2i+2。核心步驟：1.構建初始大頂堆（從最後非葉子節點向上調整）；2.排序（交換堆頂與未排序末尾元素，調整堆，重複直至完成）。C++實現包含swap、max_heapify（迭代調整子樹爲大頂堆）、heap_sort（構建堆並排序）函數，主函數測試數組排序，輸出結果正確。
閱讀全文