排序是程式設計的基石，將無序資料轉為有序序列（升冪或降冪），極大提升查詢效率。以班級成績統計為例，若依學號無序儲存，查詢最高分需遍歷所有資料；經排序後，最高分與最低分即為首尾元素，查詢複雜度從 O(n) 降為 O(1)。
相鄰元素兩兩比較，較大者前移（降冪排序）。每輪結束最小元素「沉底」，下一輪比較範圍減一。n 個元素最多需 n-1 輪。
| 輪數 | 比較次數 | 過程 | 結果 |
|---|---|---|---|
| 1 | 4 | 7↔5, 7↔8, 8↔6, 8↔9 | 5 沉底 |
| 2 | 3 | 7↔5, 7↔6, 7↔9 | 6 沉底 |
| 3 | 2 | 7↔5, 7↔9 | 7 沉底 |
| 4 | 1 | 5↔9 | 完成 |
for (i = 0; i < 10; i++)
for (j = 0; j < 10 - i; j++)
if (a[j] < a[j+1]) {
t = a[j]; a[j] = a[j+1]; a[j+1] = t;
}
引入旗標 swap，若某輪無交換發生，代表已有序，提前結束迴圈。
for (i = 0; i < 10 && !swap; i++) {
swap = 1;
for (j = 0; j < 10 - i; j++)
if (a[j] < a[j+1]) {
t = a[j]; a[j] = a[j+1]; a[j+1] = t;
swap = 0;
}
}
第一輪從首元素起，與其餘元素逐一比較，發現較大者即交換，輪末最大值落在首位。第二輪從第二位開始尋找次大值，以此類推。同樣 n 個元素最多 n-1 輪。
for (i = 0; i < 10; i++)
for (j = i+1; j < 10; j++)
if (a[i] < a[j]) {
t = a[i]; a[i] = a[j]; a[j] = t;
}
記錄最大值索引 p，僅在確定位置後執行單次交換。
for (i = 0; i < 10; i++) {
p = i;
for (j = i+1; j < 10; j++)
if (a[p] < a[j]) p = j;
if (p != i) {
t = a[i]; a[i] = a[p]; a[p] = t;
}
}
假設前 i-1 個元素已有序，將第 i 個元素插入適當位置。比較從有序區末尾向前進行，找到首個比它大的元素，插在其後；若全比較完仍未找到，則插至最前端。
for (i = 1; i < 10; i++)
for (j = i; j > 0; j--)
if (a[j] < a[j-1]) {
t = a[j]; a[j] = a[j-1]; a[j-1] = t;
}
先暫存待插值，向後位移元素騰出空位，最後一次性放入，減少賦值操作。
int a[] = {12,11,2,3,6,67,89,0,1,3};
for (i = 1; i < 10; i++) {
t = a[i];
j = i - 1;
while (j >= 0 && t > a[j]) {
a[j+1] = a[j];
j--;
}
a[j+1] = t;
}
| 演算法 | 平均時間複雜度 | 最佳情況 | 最差情況 | 穩定性 | 適用場景 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(n) 優化後 | O(n²) | 穩定 | 教學、極小資料量、近乎有序資料 |
| 選擇排序 | O(n²) | O(n²) | O(n²) | 不穩定 | 記憶體寫入成本高、資料量小 |
| 插入排序 | O(n²) | O(n) | O(n²) | 穩定 | 小規模、部分有序、線上排序 |
三大基礎排序各有優劣，理解其機制與優化技巧是進階演算法學習的基石。實務開發中，大規模資料建議使用快速排序、合併排序或語言內建庫函數（如 qsort）。排序問題更在《資料結構與演算法》中深入探討，建議持續鑽研。
