首頁  >  文章  >  堆排序是一種什麼排序

堆排序是一種什麼排序

藏色散人
藏色散人原創
2020-06-29 10:29:1910839瀏覽

堆排序是一種將無序的序列產生一個最大堆,將堆頂元素與最後一個元素對換位置,並將剩下元素產生最大堆,依序進行元素交換並產生最大堆的排序。

堆排序是一種什麼排序

堆排序

#將無序的序列產生一個最大堆,將堆頂元素與最後一個元素對換位置,將剩下元素產生最大堆,依序進行元素交換並產生最大堆

時間複雜度:O(NlogN) 空間複雜度:O(1)

簡介:

堆排序(英文:Heapsort)是指利用堆這種資料結構所設計的一種排序演算法。堆是一個近似完全二元樹的結構,並同時滿足堆積的性質:即子結點的鍵值或索引總是小於(或大於)它的父節點。

堆的操作

在堆的資料結構中,堆中的最大值總是位於根節點(在優先隊列中使用堆的話堆中的最小值位於根節點)。

堆中定義以下幾種操作:

最大堆調整(Max Heapify):將堆的末端子節點作調整,使得子節點永遠小於父節點

建立最大堆(Build Max Heap):將堆中的所有資料重新排序

堆排序(HeapSort):移除位在第一個資料的根節點,並做最大堆調整的遞歸運算 

以上是堆排序是一種什麼排序的詳細內容。更多資訊請關注PHP中文網其他相關文章!

陳述:
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn