將無序序列重排為有序（升序/降序）。以 5 元素降序為例演示三種基礎算法。
相鄰比較，大值「冒泡」上浮。每輪將當前最小值沉底，下輪比較次數 -1。
初始: 7 5 8 6 9 第1輪: 7 8 6 9 | 5 (5沉底) 第2輪: 8 7 9 | 6 5 (6沉底) 第3輪: 8 9 | 7 6 5 (7沉底) 第4輪: 9 | 8 7 6 5 (完成)
// 基礎版
for (i=0; i<n-1; i++)
for (j=0; j<n-1-i; j++)
if (a[j] < a[j+1]) swap(a[j], a[j+1]);
// 優化版：提前終止標記
for (i=0; i<n-1 && !sorted; i++) {
sorted = 1;
for (j=0; j<n-1-i; j++)
if (a[j] < a[j+1]) { swap(a[j], a[j+1]); sorted = 0; }
}
每輪在未排部分選最大值，與輪首位置交換。比較次數同冒泡，但**交換次數極少**（每輪至多 1 次）。
初始: 7 5 8 6 9 第1輪: 9 5 8 6 | 7 (9歸位) 第2輪: 9 8 5 6 | 7 (8歸位) 第3輪: 9 8 7 | 6 5 (7歸位) 第4輪: 9 8 7 6 | 5 (完成)
// 基礎版
for (i=0; i<n-1; i++)
for (j=i+1; j<n; j++)
if (a[i] < a[j]) swap(a[i], a[j]);
// 優化版：記錄最大值索引，僅交換一次
for (i=0; i<n-1; i++) {
int maxIdx = i;
for (j=i+1; j<n; j++)
if (a[maxIdx] < a[j]) maxIdx = j;
if (maxIdx != i) swap(a[i], a[maxIdx]);
}
維護有序前缀，將下一元素插入適當位置。類似整理撲克牌，對**近乎有序**數據極快（接近 O(N)）。
for (i=1; i<n; i++) {
int key = a[i], j = i-1;
while (j >= 0 && a[j] < key) { // 降序
a[j+1] = a[j];
j--;
}
a[j+1] = key;
}
| 算法 | 平均時間 | 最好情況 | 最壞情況 | 空間 | 穩定性 | 適用場景 |
|---|---|---|---|---|---|---|
| 冒泡 | 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) 算法（快排、歸併、堆排）。
