C 語言數組排序算法大全：冒泡、選擇、計數排序與優化技巧

C 語言數組排序算法大全：冒泡、選擇、計數排序與優化技巧

排序是演算法入門必修課。本文展示四種針對整型數組的排序實現，從經典冒泡、選擇排序，到利用「統計頻率」的計數排序（線性時間），並演示無臨時變量交換（XOR 交換）技巧。

1. 冒泡排序（固定最大值沉底）

void bubble_sort(int a[], int n) {
    for (int i=0; i a[j+1]) {
                a[j] ^= a[j+1];
                a[j+1] ^= a[j];
                a[j] ^= a[j+1]; // XOR 交換，無需 temp
            }
}

時間複雜度 O(n²)，穩定，原地排序。XOR 交換避免臨時變量，但現代編譯器優化下 temp 寫法同樣高效且可讀性更好。

2. 選擇排序（每輪選最小值放前）

void selection_sort(int a[], int n) {
    for (int i=0; i a[j]) {
                a[i] ^= a[j];
                a[j] ^= a[i];
                a[i] ^= a[j];
            }
}

同為 O(n²)，不穩定，交換次數少（最多 n-1 次），適合寫入成本高的存儲介質。

3. 計數排序（統計頻率，線性時間）

void counting_sort(int a[], int n, int max_val) {
    int *cnt = calloc(max_val+1, sizeof(int));
    for (int i=0; i

int cmp(const void* a, const void* b) { return *(int*)a - *(int*)b; }
qsort(arr, n, sizeof(int), cmp);