输入一个正整数数组，将它们连接起来排成一个数，输出能排出的所有数字中最小的一个。_最小组合数:输入一个正整数数组,将它们连接起来排成一个数,输出能排出的所有数字

题目： 输入一个正整数数组，将它们连接起来排成一个数，输出能排出的所有数字中最小的一个。

例如输入数组{122,12,123}，则输出这两个能排成的最小数字12122123。

思路：
新排序规则：从整数数组中取出两个数a和b,将a和b转化成字符串"a"和"b",再分别把"a"和"b"拼接成"ab"和"ba"，
再把"ab"和"ba"转出数字ab和ba，通过比较ab和ba的大小关系得出“谁排在前，谁排在后”。
1）如果ab < ba，
则a << b，数字a排在数字b的前面；（注意这里的a<<b不代表他们的大小关系，而是代表位置顺序的前后关系）
2）如果ab > ba，
则a >> b，与上面相反；
3）如果ab = ba，
则a = b，说明a和b为相同数字，谁前谁后都可以（我们按a在前b在后排）。
我们规定通过以上方式排序，能排出的数字最小。

例：如果a和b分别为12和122，那么ab和ba则分别为12122和12212；
因为12122<12212,
那么，12<<122,所以12排在122的前面。

证明（反证法）：
假设:如果存在ab>ba,那么a排在b前面得到的数最小;(接下来我们要做的是通过“a排在b前面”，看能不能推出“ab>ba”)
（1） 假设xxxxab是数组中能排出的所有数字中最小的，用ba代替ab得到xxxxba，
因为xxxxab<xxxxba则有：ab<ba，结论与假设矛盾，故不成立

（2） 假设abxxxx是数组中能排出的所有数字中最小的，用ba代替ab得到baxxxx，
因为abxxxx<baxxxx,则有：ab<ba,结论与假设矛盾，故不成立

（3） 假设axxxxb是数组中能排出的所有数字中最小的,
我们把axxxxb,整体看作ayb,y代表“xxxx”;
根据我们假设的规则等到ay<ya,yb<by;
假设a，y，b的位数分别为n，m，k(n,m,k>=1)
字符串-----对应的十进制值
ay=a * 10^m + y
ya=y * 10^n + a
yb=y * 10^k + b
by=b * 10^m + y

关系1：ay < ya
=> a * 10^m + y < y * 10^n + a
=> a * 10^m - a < y * 10^n - y
=> a( 10^m - 1)/( 10^n - 1) < y

关系2：yb < by
=> y * 10^k + b < b * 10^m + y
=> y * 10^k - y < b * 10^m - b
=> y < b( 10^m -1)/( 10^k -1)

关系3：a( 10^m - 1)/( 10^n - 1) < y < b( 10^m -1)/( 10^k -1)
=>a/( 10^n - 1)< b/( 10^k -1)
=> a10^k - a < b * 10^n - b
=>a10^k + b < b * 10^n + a
=> ab< ba
与原假设ab>ba矛盾，故原假设不成立

综上所述:得出假设不成立，从而得出结论：对于排成的最小数字，不存在满足下述关系：
如果存在ab>ba,那么a排在b前面得到的数最小。

从而得出正确的结论：如果存在ab<ba,那么a排在b前面得到的数最小。
代码

import java.util.Scanner;

public class Demo02 {
	 public static void main(String[] args){
			Scanner sc=new Scanner(System.in);
		System.out.println("请输入数组元素个数：");
			int n=sc.nextInt();
		    int[] arr=new int[n];
			System.out.println("请输入数组元素：");
			for (int i = 0; i < arr.length; i++){
				arr[i]=sc.nextInt();
			}
			  System.out.print("{");
			for (int i = 0; i < arr.length; i++){
				if(i==arr.length-1)
				System.out.print(arr[i]+"}");
				else
				System.out.print(arr[i]+",");
			}
		  System.out.println();
	     QuickSort(arr,0,arr.length-1);
	     String str="";
	 	for (int i = 0; i < arr.length; i++){
			str=str+arr[i];
		}
	 	System.out.println("最小数为:"+str);
		}
	   //快速排序
	    public static void QuickSort(int arr[],int _left,int _right){
	    	int right=_right;
	    	int left=_left;
	    	int temp=0;
	    	if(left<=right){
	    		temp=arr[left];
	    		while(left!=right){
	    			while(right>left&&Compare(arr[right],temp))
	    				right--;
	    				arr[left]=arr[right];    				
	    				while(left<right&&Compare(temp,arr[left]))
	    	 				left++;
	    					arr[right]=arr[left];    					
	    				}
	    				arr[right]=temp;
	    				QuickSort(arr,_left,left-1);
	    				QuickSort(arr,right+1,_right);    				   			  			
	    		}
	 	   }
        //按新的排序规则重写比较方法
	    public static boolean Compare(int a,int b){
				String s1=""+a;
				String s2=""+b;
				String s3=s1+s2;
				int k1=Integer.parseInt(s3);
				String s4=s2+s1;
				int k2=Integer.parseInt(s4);
	            if(k1>=k2)
	            	return true;
	            else
	            	return false;
	    }
   
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62