排序 sorting

快速排序(Quick sorting)

快速排序之觀念，找資料之中間值，將小於中間值放右邊，大於中間值放左邊，再以相同方法分左右兩邊序列，直到排序完成

【分析】

1.時間複製度，最差O(n2)與平均時間O(nlog2n)

2.需要額外堆疊空間

3.為不穩定排序

4.快速排序是平均時間最快之內部排序法

【原理】

1.取第一個記錄為鍵值K0，當中間值

2.由左而右找第一個Ki，使得Ki≧K0。由右而左找第一個Kj，使得Kj≦K0。也就是說，從左邊找比K0大，從右邊找比K0小

3.若i
4.由最大(最小)逐回合比較至最小(最大)

堆積排序(Heap sorting)

【分析】

1. 時間複製度，最差與平均時間O(nlog2n)

2. 只需一額外記錄空間

3. 為不穩定排序

【原理】

薛爾排序(Shell sorting)

【分析】

1.時間複製度，最差O(ns)與平均時間O(n(log2n)2)

2.為穩定排序