| 維度 | 冒泡排序 | 選擇排序 |
|---|---|---|
| 基本思想 | 相鄰比較，大者後移（氣泡上浮） | 每輪選出最小/最大，換到有序區末尾 |
| 交換次數 | 多（每次比較可能交換） | 少（每輪僅 1 次交換） |
| 穩定性 | 穩定（相等元素不交換順序） | 不穩定（交換可能改變相等元素相對位置） |
| 時間複雜度 | O(n²) 最好 O(n)（優化版） | O(n²) 固定，無最好情況優化 |
| 空間複雜度 | O(1) | O(1) |
| 適用場景 | 小規模、近乎有序、需穩定排序 | 小規模、交換成本高（如大結構體）、不要求穩定 |
void bubble_sort(int a[], int n) {
for (int i = 0; i < n-1; ++i) {
int swapped = 0;
for (int j = 0; j < n-1-i; ++j) {
if (a[j] > a[j+1]) {
int t = a[j]; a[j] = a[j+1]; a[j+1] = t;
swapped = 1;
}
}
if (!swapped) break; // 優化：本輪無交換提前結束
}
}
> 時交換，相等不動，保持相對順序。void selection_sort(int a[], int n) {
for (int i = 0; i < n-1; ++i) {
int min_idx = i;
for (int j = i+1; j < n; ++j)
if (a[j] < a[min_idx]) min_idx = j;
if (min_idx != i) {
int t = a[i]; a[i] = a[min_idx]; a[min_idx] = t;
}
}
}
[5a, 5b, 3] → 首輪 3 與 5a 交換 → [3, 5b, 5a]，相等元素順序顛倒。對於 n < 50 的小數據量，兩者差異可忽略；大數據量必須用 O(n log n) 算法（快排、歸併、堆排、qsort）。
