堆排序是一種將無序的序列產生一個最大堆,將堆頂元素與最後一個元素對換位置,並將剩下元素產生最大堆,依序進行元素交換並產生最大堆的排序。
堆排序
#將無序的序列產生一個最大堆,將堆頂元素與最後一個元素對換位置,將剩下元素產生最大堆,依序進行元素交換並產生最大堆
時間複雜度:O(NlogN) 空間複雜度:O(1)
簡介:
堆排序(英文:Heapsort)是指利用堆這種資料結構所設計的一種排序演算法。堆是一個近似完全二元樹的結構,並同時滿足堆積的性質:即子結點的鍵值或索引總是小於(或大於)它的父節點。
堆的操作
在堆的資料結構中,堆中的最大值總是位於根節點(在優先隊列中使用堆的話堆中的最小值位於根節點)。
堆中定義以下幾種操作:
最大堆調整(Max Heapify):將堆的末端子節點作調整,使得子節點永遠小於父節點
建立最大堆(Build Max Heap):將堆中的所有資料重新排序
堆排序(HeapSort):移除位在第一個資料的根節點,並做最大堆調整的遞歸運算
以上是堆排序是一種什麼排序的詳細內容。更多資訊請關注PHP中文網其他相關文章!