氣泡排序 vs 選擇排序：為何感覺「沒差」？
兩者**平均/最差時間複雜度皆為 O(n²)**，對小規模資料（n < 50）實測差異微小，但運作機制、資料移動次數、穩定性有本質不同：
| 特性 | 氣泡排序 | 選擇排序 |
|---|
| 核心邏輯 | 相鄰比較交換，大值像氣泡「浮」到右端 | 每趟掃描找最小值，換到左端未排序區首位 |
| 交換次數 | 最多 O(n²) 次（每次比較可能交換） | **固定 n-1 次**（每趟只交換一次） |
| 穩定性 | 穩定（相等元素不交換，相對序保持） | 不穩定（交換可能打亂相等元素順序） |
| 最佳情況 | O(n)（已有序，加旗標提前結束） | O(n²)（仍需完整掃描找最小值） |
| 適用場景 | 資料量極小、近乎有序、需穩定排序 | 寫入記憶體代價極高（如 EEPROM）、不需穩定 |
程式碼對比
// 氣泡排序（優化版）
void bubble(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(int a[], int n) {
for (int i = 0; i < n-1; i++) {
int min = i;
for (int j = i+1; j < n; j++)
if (a[j] < a[min]) min = j;
if (min != i) { int t=a[i]; a[i]=a[min]; a[min]=t; }
}
}
常見進階排序（O(n log n)）
| 演算法 | 時間複雜度 | 空間 | 穩定 | 特點 |
|---|
| 快速排序 | O(n log n) 平均 / O(n²) 最差 | O(log n) 棧 | 否 | 實務最快、原地、不穩定 |
| 合併排序 | O(n log n) | O(n) | 是 | 穩定、外部排序基礎、Linked List 友善 |
| 堆積排序 | O(n log n) | O(1) | 否 | 原地、保證 O(n log n)、緩存不友善 |
| 希爾排序 | O(n^1.3~n^1.5) | O(1) | 否 | 插入排序改良、間距序列影響大 |
| 計數/基數/桶排序 | O(n+k) | O(n+k) | 是 | 非比較排序、整數/小範圍專用 |
C 標準庫 qsort 使用範例
#include <stdlib.h>
int cmp_int(const void *a, const void *b) {
return (*(int*)a - *(int*)b); // 注意溢位風險，實務用三元比較
}
qsort(arr, n, sizeof(int), cmp_int);
選擇指南
- n < 50、教學/嵌入式小資料 → 插入排序（代碼最短、近乎有序極快）。
- 通用、追求速度 →
qsort / 快速排序 / std::sort (C++)。
- 需穩定、外部排序、Linked List → 合併排序。
- 整數、範圍已知小 → 計數/基數排序（線性時間）。
