我的程式學習路~

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 程式碼如下:

http://codepad.org/aeW3Hvob