如何用Java递归排序仅含两种不同字符的字符串？

原代码的核心问题是每次递归都会重新将smallerChar赋值为当前子串的首字符，导致无法区分全局的两个不同字符的大小关系，最终逻辑等价于直接拼接原字符串，起不到排序作用。

要解决这个问题，我们需要先确定整个字符串中两种字符的全局较小值，再基于这个固定的较小字符进行递归排序。以下是修正后的实现：

public class SortedString {

    // 主方法：对外暴露的排序入口
    private static String orderCharGroups(String text) {
        if (text.isEmpty()) {
            return "";
        }
        // 先找到全局的较小字符
        char globalSmaller = findSmallestChar(text);
        // 基于全局较小字符进行递归排序
        return sortWithFixedSmaller(text, globalSmaller);
    }

    // 辅助方法：递归找到字符串中的最小字符（仅两种字符场景）
    private static char findSmallestChar(String text) {
        if (text.length() == 1) {
            return text.charAt(0);
        }
        char current = text.charAt(0);
        char restMin = findSmallestChar(text.substring(1));
        return current < restMin ? current : restMin;
    }

    // 辅助方法：基于指定的较小字符递归排序
    private static String sortWithFixedSmaller(String text, char smallerChar) {
        if (text.isEmpty()) {
            return "";
        }
        char current = text.charAt(0);
        if (current == smallerChar) {
            // 较小字符放在前面，递归处理剩余子串
            return current + sortWithFixedSmaller(text.substring(1), smallerChar);
        } else {
            // 较大字符放在后面，递归处理剩余子串后拼接
            return sortWithFixedSmaller(text.substring(1), smallerChar) + current;
        }
    }

    public static void main(String[] args) {
        System.out.println(orderCharGroups(""));          // 输出：""
        System.out.println(orderCharGroups("1"));         // 输出："1"
        System.out.println(orderCharGroups("12"));        // 输出："12"
        System.out.println(orderCharGroups("1212"));      // 输出："1122"
        System.out.println(orderCharGroups("abbaaababbaa")); // 输出："aaaaaabbbbb"
        System.out.println(orderCharGroups("ABBA"));      // 输出："AABB"
        System.out.println(orderCharGroups("11221122"));  // 输出："11112222"
        System.out.println(orderCharGroups("AAAAAA"));    // 输出："AAAAAA"
    }
}

关键修正点说明 #

• 全局较小字符的确定：通过findSmallestChar递归遍历整个字符串，找到两种字符中的较小值，确保后续排序的判断基准是固定的。
• 分治递归排序：sortWithFixedSmaller方法基于固定的较小字符，将当前字符分为两类：较小字符直接拼在结果前面，较大字符拼在递归处理剩余子串的结果后面，最终实现所有较小字符在前、较大字符在后的排序效果。
• 符合方法限制：全程仅使用length()、isEmpty()、charAt()和substring()方法，未使用循环、数组或其他额外方法。

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