題目 1066 字符串排序：基於 ASCII 碼的冒泡排序實現與優化

題目大意

輸入長度 ≤ 20 的字符串（多組，EOF 結束），按 ASCII 碼升序排序字符，輸出排序後的字符串。

演算法選擇

數據量極小（n ≤ 20），冒泡排序 代碼簡短、穩定、無額外空間，完全足夠。亦可用 qsort/std::sort，但冒泡更適合教學展示原地交換邏輯。

冒泡排序優化版

void bubbleSort(char* s, int n) {
    for (int i = 0; i < n-1; ++i) {
        bool swapped = false;
        for (int j = 0; j < n-1-i; ++j) {
            if (s[j] > s[j+1]) {
                char tmp = s[j]; s[j] = s[j+1]; s[j+1] = tmp;
                swapped = true;
            }
        }
        if (!swapped) break; // 提前終止
    }
}

完整代碼 (C)

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int main() {
    char *buf = (char*)malloc(21); // 長度≤20 + '\0'
    while (scanf("%20s", buf) == 1) {
        int len = strlen(buf);
        for (int i = 0; i < len-1; ++i) {
            int flag = 1;
            for (int j = 0; j < len-1-i; ++j) {
                if (buf[j] > buf[j+1]) {
                    char t = buf[j]; buf[j] = buf[j+1]; buf[j+1] = t;
                    flag = 0;
                }
            }
            if (flag) break;
        }
        printf("%s\n", buf);
    }
    free(buf);
    return 0;
}

關鍵點解析

1. scanf("%20s", buf) 防止緩衝區溢出（雖然題目保證 ≤20，但防禦性編程必備）。
2. malloc(21) 動態分配，避免棧上大數組（雖然這裡無關緊要）。
3. ASCII 碼排序：數字(48-57) < 大寫(65-90) < 小寫(97-122)，符合題目要求。
4. 多組輸入以 EOF 結束，while(scanf(...)==1) 標準寫法。

複雜度

• 時間：O(T * n^2)，n≤20 → 每組 < 400 次比較，極快
• 空間：O(n)

延伸：計數排序 O(n+Σ)

若字符集固定（ASCII 128），可用計數排序：
int cnt[128]={0}; for(c: s) cnt[c]++; for(i=0;i<128;i++) while(cnt[i]--) putchar(i);
時間 O(n+128)，更優，但冒泡在 n=20 時常數更小，代碼更短。