Java递归字符串排序函数栈溢出问题及优化方案咨询

你的递归实现存在递归深度爆炸的问题：每次交换相邻字符后，会对整个字符串再次发起递归调用，导致递归次数呈指数级增长。比如处理splendid这类需要多次交换的字符串时，递归深度会达到O(n²)，远超JVM默认的调用栈容量，最终触发栈溢出。

下面提供几种更高效且无栈溢出风险的实现方式：

方法1：利用JDK内置数组排序（最简洁高效） #

直接将字符串转为字符数组，使用JDK内置的Arrays.sort（基于双轴快速排序，时间复杂度O(n log n)），再转回字符串。完全无递归，不会有栈溢出风险。

import java.util.Arrays;

public static String stringSort(String s) {
    char[] charArray = s.toCharArray();
    Arrays.sort(charArray);
    return new String(charArray);
}

方法2：迭代版冒泡排序（手动实现排序逻辑） #

如果需要手动实现类似你原逻辑的排序，改成迭代版的冒泡排序即可避免递归栈溢出。虽然时间复杂度为O(n²)，但不会占用调用栈空间。

public static String stringSort(String s) {
    char[] chars = s.toCharArray();
    int length = chars.length;
    boolean hasSwapped;
    
    for (int i = 0; i < length - 1; i++) {
        hasSwapped = false;
        // 每次循环把最大的元素"冒泡"到末尾
        for (int j = 0; j < length - i - 1; j++) {
            if (chars[j] > chars[j + 1]) {
                // 交换相邻字符
                char temp = chars[j];
                chars[j] = chars[j + 1];
                chars[j + 1] = temp;
                hasSwapped = true;
            }
        }
        // 没有交换说明已完全有序，提前终止
        if (!hasSwapped) break;
    }
    return new String(chars);
}

方法3：递归版归并排序（安全的递归实现） #

如果坚持用递归，归并排序的递归深度只有O(log n)，远低于JVM栈的上限，不会出现栈溢出。它采用分治思想，把字符串拆分成两半分别排序，再合并结果。

public static String stringSort(String s) {
    if (s.length() <= 1) {
        return s;
    }
    int mid = s.length() / 2;
    String leftSorted = stringSort(s.substring(0, mid));
    String rightSorted = stringSort(s.substring(mid));
    return mergeSortedStrings(leftSorted, rightSorted);
}

private static String mergeSortedStrings(String left, String right) {
    StringBuilder result = new StringBuilder();
    int leftIdx = 0, rightIdx = 0;
    
    while (leftIdx < left.length() && rightIdx < right.length()) {
        if (left.charAt(leftIdx) < right.charAt(rightIdx)) {
            result.append(left.charAt(leftIdx++));
        } else {
            result.append(right.charAt(rightIdx++));
        }
    }
    // 追加剩余未合并的字符
    result.append(left.substring(leftIdx));
    result.append(right.substring(rightIdx));
    
    return result.toString();
}

内容的提问来源于stack exchange，提问作者Safwan Abrar