【圖解數據結構】一組動畫徹底理解堆排序
摘要:小頂堆:每個節點的值都小於或等於其子節點的值,在堆排序算法中用於降序排列。大頂堆:每個節點的值都大於或等於其子節點的值,在堆排序算法中用於升序排列。
預備知識:堆結構
堆是具有以下性質的完全二叉樹:每個結點的值都大於或等於其左右孩子結點的值,稱爲大頂堆;或者每個結點的值都小於或等於其左右孩子結點的值,稱爲小頂堆。
堆排序
堆排序(Heapsort)是指利用堆這種數據結構(後面的【圖解數據結構】內容會講解分析)所設計的一種排序算法。堆積是一個近似完全二叉樹的結構,並同時滿足堆積的性質:即子結點的鍵值或索引總是小於(或者大於)它的父節點。堆排序可以說是一種利用堆的概念來排序的選擇排序。分爲兩種方法:
-
大頂堆:每個節點的值都大於或等於其子節點的值,在堆排序算法中用於升序排列;
-
小頂堆:每個節點的值都小於或等於其子節點的值,在堆排序算法中用於降序排列;
堆排序的平均時間複雜度爲 Ο(nlogn)。
算法步驟
-
創建一個堆 H[0……n-1];
-
把堆首(最大值)和堆尾互換;
-
把堆的尺寸縮小 1,並調用 shift_down(0),目的是把新的數組頂端數據調整到相應位置;
-
重複步驟 2,直到堆的尺寸爲 1。
來源:https://github.com/hustcc/JS-Sorting-Algorithm
算法演示
排序動畫過程解釋
-
首先,將所有的數字存儲在堆中
-
按大頂堆構建堆,其中大頂堆的一個特性是數據將被從大到小取出,將取出的數字按照相反的順序進行排列,數字就完成了排序
-
在這裏數字 5 先入堆
-
數字 2 入堆
-
數字 7 入堆, 7 此時是最後一個節點,與最後一個非葉子節點(也就是數字 5 )進行比較,由於 7 大於 5 ,所以 7 和 5 交互
-
按照上述的操作將所有數字入堆,然後從左到右,從上到下進行調整,構造出大頂堆
-
入堆完成之後,將堆頂元素取出,將末尾元素置於堆頂,重新調整結構,使其滿足堆定義
-
堆頂元素數字 7 取出,末尾元素數字 4 置於堆頂,爲了維護好大頂堆的定義,最後一個非葉子節點數字 5 與 4 比較,而後交換兩個數字的位置
-
反覆執行調整+交換步驟,直到整個序列有序
代碼實現
爲了更好的讓讀者用自己熟悉的編程語言來理解動畫,筆者將貼出多種編程語言的參考代碼,代碼全部來源於網上。
Go代碼實現
Java代碼實現
Python代碼實現
JavaScript代碼實現
如果你是 iOS開發者 ,可以在GitHub上 https://github.com/MisterBooo/Play-With-Sort-OC 獲取更直觀可調試運行的源碼。