[演算法(Algorithm)] 排序演算法(Sort Algorithm)
- 內部 & 外部排序
- 內部排序(Internal Sort)
- 資料筆數少，可以全部放到記憶體中排序
- 一般的演算法皆為內部排序
- 外部排序(External Sort)
- 資料量大，無法放到記憶體中排序，需透過其它儲存裝置輔助
- 外部排序通常會分次載入部份的資料到記憶體，用內部排序演算法排序後再回存或合併結果
- 穩定與不穩定
- 穩定(Stable)：
- 相同鍵值的資料，排序後順序和排序前一樣
-
- 排序前： 2, 7, 9, 3, 7 藍7在粉紅7前面
- 排序後： 2, 3, 7, 7, 9 藍7保持在粉紅7前面
- 不穩定(Unstable)：
- 相同鍵值的資料，排序後順序不一定和排序前一樣
-
- 排序前： 2, 7, 9, 3, 7 藍7在粉紅7前面
- 排序後： 2, 3, 7, 7, 9 藍7在粉紅7後面
- 原地置換(In-Place)
- 使用資料原來的資料結構(陣列)進行排序，不需使用暫存的輔助資料結構
- 常用排序演算法整理
| 演算法 | 時間複雜度 | 空間複雜度 | 穩定性 | 類型 |
| Best | Worst | Avg |
| 選擇排序法(Selection Sort) | Ο(n2) | Ο(n2) | Ο(n2) | Ο(1) | 不穩定 | 選擇 |
| 插入排序法(Insertion Sort) | Ο(n) | Ο(n2) | Ο(n2) | Ο(1) | 穩定 | 插入 |
| 氣泡排序法(Bubble Sort) | Ο(n) | Ο(n2) | Ο(n2) | Ο(1) | 穩定 | 交換 |
| 謝爾排序法(Shell Sort) | Ο(n) | Ο(n2)~ Ο(n1.5) | Ο(n5/4) | Ο(n) + Ο(1) | 不穩定 | 插入 |
| 搖晃排序法(Shaker Sort) | Ο(n) | Ο(n2) | Ο(n2) | Ο(1) | 穩定 | 交換 |
| 快速排序法(Quick Sort) | Ο(n log n) | Ο(n2) | Ο(n log n) | Ο(log n)~Ο(n) | 不穩定 | 交換 |
| 合併排序法(Merge Sort) | Ο(n log n) | Ο(n log n) | Ο(n log n) | Ο(n) | 穩定 | 合併 |
| 堆積排序法(Heap Sort) | Ο(n log n) | Ο(n log n) | Ο(n log n) | Ο(n) + Ο(1) | 不穩定 | 選擇 |
| 基數排序(Radix Sort) | Ο(d×(n+r)) | Ο(d×(n+r)) | Ο(d×(n+r)) | Ο(n×r) | 穩定 | 分配 |
- 常用排序演算法概念
- 選擇排序法(Selection Sort)
- 一一掃瞄未排序資料，找出最大值(or最小)
- 將最大值加入已排序的資料中
- 選擇排序法詳細介紹
- 插入排序法(Insertion Sort)
- 依序由未排序的資料中選一筆資料
- 一一掃瞄已排序資料，將選取的資料插入正確位置
- 插入排序法詳細介紹
- 氣泡排序法(Bubble Sort)
- 對未排序資料兩兩比對掃瞄
- 兩兩比對時會將未排序的最大值，介由Swap移到未排序資料中的最右邊
- 氣泡排序法詳細介紹
- 謝爾排序法(Shell Sort)
- 搖晃排序法(Shaker Sort)
- 雙向的氣泡排序法
- 每回合都會將未排序資料中的最大值移到最右邊，最小值移到最左邊
- 搖晃排序法詳細介紹
- 快速排序法(Quick Sort)
- 將比基準值(Pivot)小的數值移到左邊，比基準值大的數值移到右邊
- 對基準值的左、右子數列遞迴作相同動作
- 快速排序法詳細介紹
- 合併排序(Merge Sort)
- 將數列對分成兩個子數列，並遞回對分
- 對分至只有一個元素時，將元素回傳合併
- 合併排序法詳細介紹
- 堆積排序(Heap Sort)
- 利用堆積樹(Heap Tree)的性質來排序
- 最大堆積樹(Max Heap Tree)的根節點一定是最大值，一一與最後一個樹葉節點交換後，取出加入已排序數列
- 將原來的樹重新調整為最大堆積樹
- 堆積排序法詳細介紹
- 基數排序(Radix Sort)