编辑代码

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Hashtable;
import java.util.List;
 
public class Main {
 
	public static void main(String[] args) {
 
		 long a=System.currentTimeMillis();
		
		 String s="11234445678";
		 char[] arr=s.toCharArray();
		 Arrays.sort(arr);
		 List<String> result=new ArrayList<String>();
		 result.add(String.valueOf(arr));
		while(lowPos(arr)!=-1){
			int i=lowPos(arr);
			int j=minInMaxThanPos(arr, i);
			swap(arr, i, j);
			reverseAfterI(arr, i);
			result.add(String.valueOf(arr));
		 }
		System.out.println(result.size());
		long b=System.currentTimeMillis();
		System.out.println("用时："+String.valueOf(b-a));
	    //for(String e:result)
			//System.out.println(e);                 
	}
	
	//从排列的右端开始，找出第一个比它的右边的字符（紧挨着它的）小的字符的序号
	//比如在"839647521" 自右至左找出排列中第一个比右边数字小的数字是'4' ，返回它的下标4
	public static int lowPos(char[] arr){
		
		int i;
		for(i=arr.length-1;i>=1;i--)
			if(arr[i-1]<arr[i])
				break;
		return i-1;
		
	}
	
	//在下标index的右边的字符中，找出所有比arr[index]大的字符中的最小的字符的下标
	//比如在"839647521" index=4时，arr[4]='4',
	// 在'4'右边所有大于'4'的字符中的最小者是'5',返回'5'的下标6
	public static int minInMaxThanPos(char[] arr,int index){
		
		Hashtable< Character,Integer> ht=new Hashtable< Character,Integer>();
		ArrayList<Character> tmp =new ArrayList<Character>();
		int j=0;
		for(int i=index+1;i<arr.length;i++)
			if(arr[i]>arr[index])
				{
				  ht.put(arr[i],i);
				  tmp.add(arr[i]);
				 
				}
		if( ht.isEmpty())
			return -1;
		
		Collections.sort(tmp);
		return  ht.get(tmp.get(0));
		
	}
	//交换
	public static void swap(char[] arr,int i,int j){
		
		char tmp=arr[i];
		arr[i]=arr[j];
		arr[j]=tmp;
	}
	// arr 在 index之后的元素反转
	//比如在"839647521" 在index=6之后的元素反转是："839647512"
	public static void reverseAfterI(char[] arr,int index){
		
		int j=arr.length-1;
		//arr 在 index之后的元素的长度
		int len=arr.length-1-(index+1)+1;
		for(int i=index+1;i<=index+len/2;i++)
			swap(arr,i,j--);
	}
}