資料結構：排序
排序（Sorting）是資料結構與演算法中最常見且最重要的操作之一。排序的目的是將一組無序的資料按照特定順序重新排列，以便後續查找、搜尋或進行其他運算更加高效。
一、排序的意義與應用
- 快速搜尋： 排序後的資料可以使用二分搜尋法等高效搜尋演算法。
- 資料分析： 資料排序後便於觀察資料的趨勢、分佈情況。
- 去除重複： 排序後可以輕鬆辨識重複資料。
- 最佳化處理： 某些演算法在處理有序資料時表現更佳，如雙指針技術。
二、排序的分類
排序演算法大致可分為以下兩類：
1. 比較排序（Comparison Sort）
通過比較元素大小來確定排序順序，時間複雜度下限為 $O(n \log n)$。
常見的比較排序方法有：
- 冒泡排序（Bubble Sort）
- 選擇排序（Selection Sort）
- 插入排序（Insertion Sort）
- 歸併排序（Merge Sort）
- 快速排序（Quick Sort）
- 堆積排序（Heap Sort）
2. 非比較排序（Non-comparison Sort）
不依賴元素間比較，而是根據元素特性進行排序，時間複雜度可達線性 $O(n)$。
常見的非比較排序方法有：
- 計數排序（Counting Sort）
- 基數排序（Radix Sort）
- 桶排序（Bucket Sort）
三、常見排序演算法解析
1. 冒泡排序（Bubble Sort）
逐個比較相鄰元素，若順序錯誤則交換，直至整個陣列有序。
- 時間複雜度：$O(n^2)$
- 穩定性：穩定
2. 選擇排序（Selection Sort）
每輪從未排序部分選擇最小（或最大）元素，放置於已排序部分末尾。
- 時間複雜度：$O(n^2)$
- 穩定性：不穩定
3. 插入排序（Insertion Sort）
將元素插入到已排序部分的適當位置，逐步擴大排序區域。
- 時間複雜度：$O(n^2)$
- 穩定性：穩定
4. 歸併排序（Merge Sort）
採用分治法，將陣列劃分為兩部分，分別排序後合併。
- 時間複雜度：$O(n \log n)$
- 穩定性：穩定
5. 快速排序（Quick Sort）
選擇一個基準值，將陣列分為小於與大於基準值的兩部分，遞迴排序。
- 時間複雜度：平均 $O(n \log n)$，最壞 $O(n^2)$
- 穩定性：不穩定
6. 堆積排序（Heap Sort）
將陣列轉換為最大堆或最小堆，每次取堆頂元素，重新調整堆。
- 時間複雜度：$O(n \log n)$
- 穩定性：不穩定
7. 計數排序（Counting Sort）
統計各個元素出現次數，再依次輸出。
- 時間複雜度：$O(n + k)$，$k$ 為數值範圍
- 穩定性：穩定
8. 基數排序（Radix Sort）
按照數字位數逐位比較，例如個位、十位、百位依次排序。
- 時間複雜度：$O(n \cdot d)$，$d$ 為數字長度
- 穩定性：穩定
9. 桶排序（Bucket Sort）
將數據分散到多個桶中，桶內使用其他排序演算法，最後合併。
- 時間複雜度：$O(n + k)$，$k$ 為桶數
- 穩定性：視桶內排序而定
四、排序演算法性能比較
| 排序演算法 | 平均時間複雜度 | 最壞時間複雜度 | 穩定性 |
|---|---|---|---|
| 冒泡排序 | $O(n^2)$ | $O(n^2)$ | 穩定 |
| 選擇排序 | $O(n^2)$ | $O(n^2)$ | 不穩定 |
| 插入排序 | $O(n^2)$ | $O(n^2)$ | 穩定 |
| 歸併排序 | $O(n \log n)$ | $O(n \log n)$ | 穩定 |
| 快速排序 | $O(n \log n)$ | $O(n^2)$ | 不穩定 |
| 堆積排序 | $O(n \log n)$ | $O(n \log n)$ | 不穩定 |
| 計數排序 | $O(n + k)$ | $O(n + k)$ | 穩定 |
| 基數排序 | $O(n \cdot d)$ | $O(n \cdot d)$ | 穩定 |
| 桶排序 | $O(n + k)$ | $O(n^2)$ | 視桶內而定 |
五、選擇排序演算法的考量
- 資料規模： 小規模資料可選擇簡單排序，如插入排序；大規模資料選擇快速排序或歸併排序。
- 資料性質： 若資料接近有序，可選擇插入排序；若資料範圍小，可使用計數排序。
- 穩定性需求： 若排序過程須保持相同元素的原始順序，選擇穩定排序。
六、結論
排序演算法是程式設計與資料處理的基礎，不同場景選擇合適的排序方法，可提升演算法效率與程式性能。熟悉各種排序的特性，有助於在實務開發中做出最佳選擇。