247
堆排序+代碼實現
堆排序
堆,heap,是二叉樹的一種。小根堆有這樣的性質——任意一個結點的值比它的左右孩子都要小。
排序思想
將待排元素看作是完全二叉樹，物理上用一維數組存儲。
實現堆排序需要解決兩個問題：
1.如何將雜亂的完全二叉樹初始化為一個堆？
答：從最後一個非葉結點起，將該節點當做根，自上而下進行調整，使之成為一個堆。然後依次對倒數第二個、倒數第三個、直至正數第一個結點進行此操作。
2.輸出堆頂元素後，如何將餘下的元素調整為一個堆？
答：將最後一個結點放在原根結點位置上，以它為根進行上述的調整。
複雜度分析。
二叉樹的層數計算方法，從上往下，1,2,3,4......
耗時的操作有構造初始堆和調整堆兩部分。
對深度為h的堆進行自上而下的調整，最多比較次數為2*(h-1)。
在初始化堆的過程中，完全二叉樹的高度為h，總的比較次數為
綜上，堆排序在複雜度最壞的情況下為O((1)式+(2)式)=O(n*logn)。
代碼
初始序列為1 8 6 2 5 4 7 3一組數采用堆排序，當建堆（小根堆）完畢時，堆所對應的二叉樹中序遍曆序列為：（A）
A．8 3 2 5 1 6 4 7 B．3 2 8 5 1 4 6 7 C．3 8 2 5 1 6 7 4 D．8 2 3 5 1 4 7 6
最後更新：2017-04-03 05:40:19