高等排序法的平均時間複雜度為:O(n*logn)
快速排序法(Quick sort)
步驟:
1.取第一筆作為控制鍵(pivot key)
2.由左向右開始找(i=1,2,3,....)，找到一筆值K(i)>pivot key(意思就是找大)
由右向左開始找(j=1,2,3,....)，找到一筆值K(j)<pivot key(意思就是找小)
3.將K(i)與K(j)交換，並退回步驟二，如果i與j交錯，\則stop，將pivot key與K(j)交換
與insertion sort不同的是insertion是將K(i)的值放在部分以排序好的資料中，但quick sort是將值放在整個檔案中正確的位置上。
EX:
| init | [5] | 3 | 2 | 7 | 1 |
| 1 | 1 | 3 | 2 | [5] | 7 |
說明:第一次k(i)=7,k(j)=1，swap後->5,3,2,1,7
當i,j繼續探索，發現i與j交錯，所以stop，並切將K(j)=1與pivot key=5交換
變為:1,3,2,5,7
1.時間複雜度:
最好，平均:O(n*logn)
最差:O(n²)
(如果遇到降序或升序的排序組合，則n 筆數字都會成為pivot key，比較(n-1)次=n(n-1)次
2.為Unstable sort
3,2,5,5+,1
3,2,1,5+,5 (交換後位置改變)
合併排序法(Merge sort)
將兩筆以排序好的檔案儲存成另一筆排序好的檔案。
1.時間複雜度:
最好、最差、平均:O(n*logn)
2.為一stable sort
3.需要額外的空間O(n)，為一外部搜尋法
堆積排序法(Heap sort)
1:需要先建立一顆complete binary tree
2:調整成heap tree並輸出heap tree的root
3:將最後一個節點的直放去root，再回到步驟2
分析:
1.時間複雜度:
最好，最差，平均:O(n*logn)
2.space complexity:O(1)
3.Unstable sort
因為在Top-down的調整過程中會刪除最後節點，移至root，5,5+位置會交換。
EX:7,5+,1,2,5
->7,5,5+,2,1
heap tree 的定義
Max(Min) heap tree:
1.為一顆complete binary tree
2.root為最大(小)值
3.父節點>(<)子節點
建立heap tree 有兩種method:
1.top down(add one by one):
T.C.為:O(n)
2.buttom up(arrange in once)
T.C.為:O(logn)
