题解 | #图片整理#

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		while(sc.hasNext()){
			char[] chars = sc.next().toCharArray(); 
			chars = quickSort(chars, 0, chars.length-1);
			
			System.out.println(chars);
		}
		
		sc.close();
	}

	
	public static char[] quickSort(char[] chars, int begin, int end){
		
		//初始化
		int ref = begin;//参考值初始定为第1个
		int ptr = begin+1;//左边指针ptr，向右移动
		int ptr1 = end;//右边指针ptr1，向左移动
		
		//while循环开始，循环结束后分界线确定，进入递归。
		while(ptr <= ptr1){//左右指针可相遇重合，即ptr==ptr1
			
			//移动右指针，直到遇到符合条件的才停下来
			while(chars[ptr1] > chars[ref] && ptr < ptr1){//右指针此时一定是在参考值左边的。当遇到比参考值小的，或者遇到左指针（不重合），就停止移动
				ptr1--;
			}
			
			
			//参考值与右指针交换
			if(ptr < ptr1){//交换前先判断左右指针是否重合，指针重合的情况单独拿出来讨论
				
				if(chars[ref] > chars[ptr1]){//两边的值相等时，省去交换操作，只变更参考指针。
					chars = swap(chars, ref, ptr1);
				}
				
				//更新参考指针
				ref = ptr1;
				
			}
			
			//移动左指针，直到遇到符合条件的才停下来。
			while(chars[ptr] < chars[ref] && ptr < ptr1){//左指针此时一定是在参考值左边的。当遇到比参考值大的，或者遇到右指针（不重合），就停止移动。
				ptr++;
			}
			
			//参考值与左指针交换
			if(ptr < ptr1){//指针不重合。重合的情况后面单独处理。
				if(chars[ptr] > chars[ref]){//两边的值相等时，省去交换操作，只变更参考指针。
					chars = swap(chars, ptr, ref);
				}
				
				//更新参考指针
				ref = ptr;
				
				//等左右各交换一次后，右指针左移一下（试过如果提前移动，会出错，懒得深究了）
			    ptr1--;
			    
			}
			
			//此时判断一下指针是否重合，重合的话需要处理一下。而且此时重合点一定是在参考值右边的。
			if(ptr == ptr1){
				if(chars[ptr1] < chars[ref]){//重合点的值比参考值小，就交换一下
					chars = swap(chars, ref, ptr1);
				}else{
					//重合点比参考值大或相等（相等的留给递归处理），则不做任何动作
					break;
				}
			}
		}
		
		
		//开始递归左边和右边
		if(begin < ref-1){//递归把参考值左边部分排好序。直到数组细分到只剩1个的长度。
			
			
			chars = quickSort(chars, begin, ref-1);//递归调用
		}
		
		if(ref+1 < end){//递归把参考值左边部分排好序。直到数组细分到只剩1个的长度。
			
			chars = quickSort(chars, ref+1, end);//递归调用
		}
		return chars;
		
	}
	
	public static char[] swap(char[] chars, int i, int j){
		char temp = chars[i];
		chars[i] = chars[j];
		chars[j] = temp;
		return chars;
	}
}