C 語言字符串重排：字母前數字後且保持相對順序的穩定分區算法實現

題目要求

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

算法分析：穩定分區

• 普通快速排序/雙指針交換**不穩定**，會打亂相對順序。
• 需採用**穩定分區**思路：掃描兩次或輔助數組。
• 空間換時間：O(n) 時間，O(n) 空間，最簡清晰。

標準實現 (輔助數組法)

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

#define MAX_LEN 1024

int main() {
    char str[MAX_LEN];
    char result[MAX_LEN];
    int idx = 0;

    printf("輸入字符串: ");
    fgets(str, MAX_LEN, stdin);  // 安全替代 gets()
    str[strcspn(str, "\n")] = '\0'; // 去除換行

    // 第一遍：收集字母
    for (int i = 0; str[i]; i++) {
        if (isalpha((unsigned char)str[i])) {
            result[idx++] = str[i];
        }
    }
    // 第二遍：收集數字
    for (int i = 0; str[i]; i++) {
        if (isdigit((unsigned char)str[i])) {
            result[idx++] = str[i];
        }
    }
    // 其他字符(符號/空格)按需求決定是否保留，題目未提及，此處忽略

    result[idx] = '\0';
    printf("結果: %s\n", result);
    return 0;
}

進階：原地穩定分區 (O(1) 空間，O(n²) 時間)

若嚴禁輔助數組，可用「旋轉/插入」思想：

// 找到第一個數字位置 left
// 從 left+1 掃描，遇到字母則將 [left, i-1] 右旋一位，字母插入 left，left++
// 類似插入排序，保證穩定，但時間複雜度退化為 O(n²)

**面試/考試首選輔助數組法**，代碼簡潔、可讀性強、符合穩定性要求；僅在嵌入式極度受限內存時考慮原地算法。

關鍵細節

• isalpha/isdigit 需轉換為 unsigned char 避免負值未定義行為 (C 標準要求)。
• 使用 fgets 替代危險的 gets (已從 C11 移除)。
• 輸入長度未知時，動態分配內存 malloc(strlen(str)+1) 更健壯。

「兩遍掃描 + 輔助數組」是解決穩定分區問題的通用模板，同樣適用於「奇偶分離、正負分離、自定義條件分區」等場景。