题意整理。

• 输入一行字符串，不区分大小写从小到达排序。
• 如果大小写字母同时出现，按输入顺序排列。如果是非英文字母类型的字符，保持原来位置不变。

方法一（自定义排序）

1.解题思路

• 首先将字符串转换为字符数组，将字符数组中的字母添加到一个list容器。
• 然后自定义排序规则，不区分大小写，从小到大排序。
• 最后遍历字符数组，同时预先定义一个索引变量，如果是字母类型，则按list中的顺序给字符数组对应位置赋值，否则，原来位置保持不变。接着将字符数组转换为字符串形式输出。

图解展示：

2.代码实现

import java.util.Scanner;
import java.util.ArrayList;
import java.util.Collections;

public class Main{
    public static void main(String[] args){
        //标准输入
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()){
            //输入字符串
            String s=sc.nextLine();
            //转换为字符数组
            char[] arr=s.toCharArray();
            //用于存储arr中的字母类型字符
            ArrayList<Character> list=new ArrayList<>();
            for(char c:arr){
                //如果是字母，加入到list
                if(Character.isLetter(c)){
                    list.add(c);
                }
            }
            //不区分大小写，从A到Z排列
            Collections.sort(list,(c1,c2)->Character.toLowerCase(c1)-Character.toLowerCase(c2));
            int id=0;
            for(int i=0;i<arr.length;i++){
                //如果是字母，按新顺序排列，否则，保持原来位置不变
                if(Character.isLetter(arr[i])){
                    arr[i]=list.get(id++);
                }
            }
            System.out.println(String.valueOf(arr));
        }            
    }
}

3.复杂度分析

• 时间复杂度：需要遍历字符数组，和对字符数组进行自定义排序，遍历的时间复杂度为$O(n)O(n)$，排序的时间复杂度为$O(n\ast lo{g}_{2}n)O(n*log\_2n)$，所以时间复杂度为$O(n\ast lo{g}_{2}n)O(n*log\_2n)$。
• 空间复杂度：需要额外大小为n的list容器，所以空间复杂度为$O(n)O(n)$。

方法二（利用io流）

1.解题思路

思路和方法一基本一致，不同的是通过io流操作来处理输入的数据。

2.代码实现

import java.io.*;
import java.util.ArrayList;
import java.util.Collections;

public class Main{
    public static void main(String[] args) throws Exception{
        //io输入
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        //记录输入的字符串
        String s;
        while((s=br.readLine())!=null){
            //转换为字符数组
            char[] arr=s.toCharArray();
            //用于存储arr中的字母类型字符
            ArrayList<Character> list=new ArrayList<>();
            for(char c:arr){
                //如果是字母，加入到list
                if(Character.isLetter(c)){
                    list.add(c);
                }
            }
            //不区分大小写，从A到Z排列
            Collections.sort(list,(c1,c2)->Character.toLowerCase(c1)-Character.toLowerCase(c2));
            int id=0;
            for(int i=0;i<arr.length;i++){
                //如果是字母，按新顺序排列，否则，保持原来位置不变
                if(Character.isLetter(arr[i])){
                    arr[i]=list.get(id++);
                }
            }
            System.out.println(String.valueOf(arr));
        }            
    }
}

3.复杂度分析

• 时间复杂度：需要遍历字符数组，和对字符数组进行自定义排序，遍历的时间复杂度为$O(n)O(n)$，排序的时间复杂度为$O(n\ast lo{g}_{2}n)O(n*log\_2n)$，所以时间复杂度为$O(n\ast lo{g}_{2}n)O(n*log\_2n)$。
• 空间复杂度：需要额外大小为n的list容器，所以空间复杂度为$O(n)O(n)$。