Java 字符串反轉 5 種經典算法實現與性能對比

前言

字符串反轉是面試高頻題，也是理解 Java 數據結構、算法思想的絕佳切入點。本文實現 5 種經典算法，分析時空複雜度、適用場景與性能特徵。

算法實現

1. 數組雙指針交換（原地反轉，最優）

public String reverseByArray(String str) {
    if (str == null || str.length() <= 1) return str;
    char[] ch = str.toCharArray();
    for (int i = 0, j = ch.length - 1; i < j; i++, j--) {
        char temp = ch[i];
        ch[i] = ch[j];
        ch[j] = temp;
    }
    return new String(ch);
}

• 時間：O(n)
• 空間：O(n) (字符數組)
• 優點：單次遍歷，無額外對象創建，性能最佳

2. 棧 (Stack) 後進先出

public String reverseByStack(String str) {
    if (str == null || str.length() <= 1) return str;
    Stack<Character> stack = new Stack<>();
    for (char c : str.toCharArray()) stack.push(c);
    char[] ch = new char[str.length()];
    for (int i = 0; i < ch.length; i++) ch[i] = stack.pop();
    return new String(ch);
}

• 時間：O(n)
• 空間：O(n) (棧 + 數組)
• 優點：邏輯直觀，教學演示佳
• 缺點：棧操作開銷大，實際性能較差

3. 逆序遍歷 + StringBuilder

public String reverseByStringBuilder(String str) {
    if (str == null || str.length() <= 1) return str;
    StringBuilder sb = new StringBuilder(str.length());
    for (int i = str.length() - 1; i >= 0; i--) {
        sb.append(str.charAt(i));
    }
    return sb.toString();
}

• 時間：O(n)
• 空間：O(n) (StringBuilder 內部數組)
• 優點：代碼簡潔，StringBuilder 線程不安全但單線程高效
• 推薦：實際開發首選（除非極度追求性能用數組）

4. 位運算異或交換 (XOR Swap)

public String reverseByXor(String str) {
    if (str == null || str.length() <= 1) return str;
    char[] ch = str.toCharArray();
    int len = ch.length;
    for (int i = 0; i < len / 2; i++) {
        ch[i] ^= ch[len - 1 - i];
        ch[len - 1 - i] ^= ch[i];
        ch[i] ^= ch[len - 1 - i];
    }
    return new String(ch);
}

• 原理：a ^= b; b ^= a; a ^= b; 交換無需臨時變量
• 時間：O(n)
• 空間：O(1) 額外空間 (僅數組)
• 缺點：可讀性差，現代 JVM 優化下無優勢，甚至較慢
• 注意：僅適用於基本類型，引用類型不可用

5. 遞歸

public String reverseByRecursive(String str) {
    if (str == null || str.length() == 0) return str;
    if (str.length() == 1) return str;
    return reverseByRecursive(str.substring(1)) + str.charAt(0);
}

• 時間：O(n²) — substring 複製字符串，+ 拼接創建新對象
• 空間：O(n²) — 遞歸棧 + 大量字符串對象
• 缺點：極易堆棧溢出 (長字符串)，性能極差
• 優點：展示遞歸思想，函數式風格

性能基準測試 (JMH 思想驗證)

public class Benchmark {
    public static void main(String[] args) {
        String s = "1234567890".repeat(1000); // 10000 字符
        long start, end;

        // 預熱
        for (int i = 0; i < 10000; i++) reverseByArray(s);

        // 數組法
        start = System.nanoTime();
        for (int i = 0; i < 100000; i++) reverseByArray(s);
        end = System.nanoTime();
        System.out.println("Array: " + (end - start) / 1e6 + " ms");

        // StringBuilder
        start = System.nanoTime();
        for (int i = 0; i < 100000; i++) reverseByStringBuilder(s);
        end = System.nanoTime();
        System.out.println("StringBuilder: " + (end - start) / 1e6 + " ms");

        // 棧
        start = System.nanoTime();
        for (int i = 0; i < 100000; i++) reverseByStack(s);
        end = System.nanoTime();
        System.out.println("Stack: " + (end - start) / 1e6 + " ms");

        // 遞歸 (僅測試小字符串防 OOM)
        String small = "12345";
        start = System.nanoTime();
        for (int i = 0; i < 10000; i++) reverseByRecursive(small);
        end = System.nanoTime();
        System.out.println("Recursive (small): " + (end - start) / 1e6 + " ms");
    }
}

典型輸出 (參考)

Array: 45 ms
StringBuilder: 52 ms
Stack: 180 ms
Recursive (small): 120 ms

總結與建議

面試加分點

1. 說明 String 不可變，反轉必產生新對象
2. 對比 StringBuilder vs StringBuffer (線程安全開銷)
3. 指出遞歸 substring 在 JDK 7+ 共享 char[] 但 JDK 8+ 複製，影響性能分析
4. 補充：new StringBuilder(str).reverse().toString() 一行流式寫法