排序 sorting

常見之排序演算法

常見之排序演算法：氣泡排序、選擇排序、插入排序、快速排序、堆積(heap)排序、薛爾(shell)排序、合併排序、基數排序

氣泡排序(Bubble sorting)

資料結構中最簡單之排序法。所謂氣泡排序法就是相臨資料互相比較，若發現資料順序不對，就將資料互換。依次由上往下比，則結果將如氣泡般，依次由下往上浮起。

【分析】

1.比較之回合數=資料數(n)-1

2.每一回合至少有一資料可以排列至正確之次序

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

4.需要一個額外(元素)空間

5.為一穩定排序

6.資料量小時，使用效果佳

【原理】

1. 每一回合逐一比較相臨資料，依排序之順序交換位置

2.每回合至少會有一次交換位置，至沒交換位置則停止

選擇排序(Selection sorting)

類似於氣泡排序法。主要差異在於，第n回合比較時，以一額外資料空間儲存目前第n大(小)，若發現資料順序不對，就將資料互換。依次由上往下比，則結果將由最大(最小)逐回合比較至最小(最大)。

【分析】

1.比較之回合數=資料數(n)-1

2.時間複製度：最差與平均時間O(n2)

3.需要一個額外(元素)空間

4.為一穩定排序

5.資料量小時，使用效果佳(優於氣泡)

【原理】

1.未排序前之第一筆資料可視為已排序好之資料

2.每一回合逐一比較相臨資料，依排序之順序交換位置。

插入排序(Insertion sorting)

每次往後拿一筆記錄，依大小插入已排序好的記錄。也就是說，差入一個記錄在一堆已排好序之記錄中。任何未排序前之第一筆資料可視為已排序好之資料。

【分析】

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

2.只需要一個額外(元素)空間

3.為一穩定排序。

4.此方法適用於大部份資料已排序或已排序之資料庫新增資料後進行排序

【原理】

1.將待排序之資料逐一與已排序後之資料比較，再將資料放入適當位置

2.由最大(最小)逐回合比較至最小(最大)