1、建構初始堆:
初始化堆的時候是對所有的非葉子結點進行篩選。
最後一個非終端元素的下標是[n/2]向下取整,所以篩選只需要從第[n/2]向下取整個元素開始,從後往前進行調整。
例如,給定一個數組,首先根據該數組元素建構一個完全二元樹。
然後從最後一個非葉子結點開始,每次都是從父結點、左孩子、右孩子中進行比較交換,交換可能會引起孩子結點不滿足堆的性質,所以每次交換之後需要重新對被交換的孩子結點進行調整。
2、進行堆排序:
有了初始堆之後就可以進行排序了。
堆排序是一種選擇排序。建立的初始堆為初始的無序區。
排序開始,首先輸出堆頂元素(因為它是最值),將堆頂元素和最後一個元素交換,這樣,第n個位置(即最後一個位置)作為有序區,前n-1個位置仍是無序區,對無序區進行調整,得到堆之後,再交換堆頂和最後一個元素,這樣有序區長度變成2。 。 。
不斷進行此操作,將剩餘的元素重新調整為堆,然後輸出堆頂元素到有序區。每次交換都導致無序區-1,有序區 1。不斷重複此過程直到有序區長度增長為n-1,排序完成。
3、堆疊排序實例:
首先,建立初始的堆疊結構如圖:
然後,交換堆頂的元素和最後一個元素,此時最後一個位置作為有序區(有序區顯示為黃色),然後進行其他無序區的堆調整,重新得到大頂堆後,交換堆頂和倒數第二個元素的位置…
#重複此過程:
最後,有序區擴展完成即排序完成:
由排序過程可見,若想得到升序,則建立大頂堆,若想得到降序,則建立小頂堆。
以上是堆排序怎麼排的詳細內容。更多資訊請關注PHP中文網其他相關文章!