题解 | #字符串排序#

基数排序

过滤掉字符，进行基数排序，由于要考虑大小写出现的顺序，使用链表记录每一个字符，到时候按序输出即可。

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            String s = in.nextLine();
            
            // 记录字母排序，类似基数排序
            List<List<Character>> buckets = new ArrayList<>();
            for(int i = 0; i < 26; i++) {
                buckets.add(new ArrayList<>());
            }
            char[] str = s.toCharArray();
            for(int i = 0; i < str.length; i++) {
                char ch = str[i];
                if(Character.isLetter(ch))
                    buckets.get(Character.toLowerCase(ch) - 'a').add(ch);
            }

            int buck = 0;
            int buckId = 0;
            for(int i = 0; i < str.length; i++) {
                if(Character.isLetter(str[i])) {
                    while(buckId >= buckets.get(buck).size()) {
                        // 寻找下一个桶
                        buck++;
                        buckId = 0;
                    }

                    // 直接修改数组
                    str[i] = buckets.get(buck).get(buckId++);
                }
            }

            System.out.println(String.valueOf(str));
        }
    }
}