A 講解:
堆排序法 平均時間複雜度Θ(n lg n) 最差最優都是O(n lg n)
概念就是當資料一個個讀進來時
就用"插入" (Insert)建構一個最大堆
建立好後 將第一個元素(最大) 和最後一個元素交換 此步驟即類似"刪除"(delete)指令
接著 把最後一個元素視為"已排序" 排除在堆之外
而前面的元素仍然在最大堆之中
持續操作直至堆的大小為"1"
此時除了第一個元素外 其他皆是被排序好的
但是 第一個值因為是最大堆最後一個元素 所以一定是這筆資料中最小的
所以何起來就是一個以排序清單囉!
用圖形解說如下:
一筆測資 {15, 11, 27, 3, 9, 58, 22, 1, 17}
建立好最大堆時 應該是呈現這樣 {58, 17, 27, 11, 9, 15, 22, 1, 3}
接著 進入到 Heap_Sort函式時(參見程式碼)
一步步如下:
[27 17 22 11 9 15 3 1] (58) * []表示為最大堆 ()表示為已排序好資料
[22 17 15 11 9 1 3] (27 58)
[17 11 15 3 9 1] (22 27 58)
.
.
.
[1] (3 9 11 15 17 22 27 58)
B 範例例題如下:
先輸入資料數 即陣列大小
接著輸入一筆未排序測資
請輸出排序後資料 並在每筆測資後空一行
EX:
Input:
9
15 11 27 3 9 58 22 1 17
Output:
1 3 9 11 15 17 22 27 58
C 程式碼如下:
全站熱搜