C 語言字串重新排列：字母優先、數字其次，保持相對順序

題目

輸入一字串，重新排列使所有字母 (A-Z, a-z) 在前，數字 (0-9) 在後，且字母間、數字間的原始相對順序不變。

例：`"a1b2c3"` → `"abc123"`

演算法：雙指針/雙緩衝區 (O(n) 時間、O(n) 空間)

掃描一次，字母存入 `letters[]`，數字存入 `digits[]`，最後合併。

C 語言實作

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

void reorder(char *str) {
    int len = strlen(str);
    char *letters = malloc(len + 1);
    char *digits  = malloc(len + 1);
    int l = 0, d = 0;

    for (int i = 0; i < len; i++) {
        if (isalpha((unsigned char)str[i])) {
            letters[l++] = str[i];
        } else if (isdigit((unsigned char)str[i])) {
            digits[d++] = str[i];
        }
        // 其他字元可選擇保留或丟棄
    }
    letters[l] = '\0';
    digits[d] = '\0';

    strcpy(str, letters);
    strcat(str, digits);

    free(letters);
    free(digits);
}

int main(void) {
    char str[100];
    printf("輸入字串: ");
    fgets(str, sizeof(str), stdin);
    str[strcspn(str, "\n")] = '\0'; // 移除換行

    reorder(str);
    printf("結果: %s\n", str);
    return 0;
}

原地演算法 (O(1) 空間、O(n²) 時間)

類似插入排序：從左掃描到第一個數字，之後遇到字母則向前插入至數字區塊之前。適合嵌入式記憶體受限環境。

關鍵點

• 使用 `ctype.h` 的 `isalpha`、`isdigit` 判斷，支援區域設定。
• `unsigned char` 轉型避免負值導致未定義行為。
• 保持相對順序 → 穩定分區 (Stable Partition)。

C++ STL 一行解

std::stable_partition(s.begin(), s.end(), [](char c){ return std::isalpha(c); });

總結

雙緩衝區法簡單高效，符合大多數應用場景。若面試要求原地演算法，可說明「穩定分區」思路並給出插入式實作。