將無序資料轉變為有序序列的經典演算法
排序演算法可分為比較排序與非比較排序兩大類。比較排序的理論下限為 O(n log n)，而非比較排序可達到 O(n)。
氣泡排序 (Bubble Sort)：重複走訪數列，相鄰元素兩兩比較，大的向後移。時間 O(n²)，空間 O(1)。
合併排序 (Merge Sort)：分治策略，將數列分成兩半分別排序再合併。時間 O(n log n)，空間 O(n)。
快速排序 (Quick Sort)：選 pivot 分區，左小右大。平均 O(n log n)，最壞 O(n²)。
堆積排序 (Heap Sort)：利用最大堆積進行排序。時間 O(n log n)，空間 O(1)。
| 演算法 | 最好 | 平均 | 最壞 | 空間 | 穩定 |
|---|---|---|---|---|---|
| 氣泡排序 | O(n) | O(n²) | O(n²) | O(1) | 是 |
| 選擇排序 | O(n²) | O(n²) | O(n²) | O(1) | 否 |
| 插入排序 | O(n) | O(n²) | O(n²) | O(1) | 是 |
| 合併排序 | O(n log n) | O(n log n) | O(n log n) | O(n) | 是 |
| 快速排序 | O(n log n) | O(n log n) | O(n²) | O(log n) | 否 |
| 堆積排序 | O(n log n) | O(n log n) | O(n log n) | O(1) | 否 |