把数组排成最小的数

方法一：使用贪心算法，每次选择一个最大优先级的数字放在最后（类似于冒泡排序），对于优先级的比较，使用cmp函数即可，正向拼接n1与n2，反向拼接n2与n1,正向字符串大，则说明n1优先级最大，放在最后。

public class Solution {
    public String PrintMinNumber(int [] numbers) {
        for(int i=0;i<numbers.length-1;++i){
            for(int j=0;j<numbers.length-i-1;++j){
                if(cmp(numbers[j],numbers[j+1])){
                    int temp = numbers[j];
                    numbers[j] = numbers[j+1];
                    numbers[j+1] = temp;
                }
            }
        }
        String res = "";
        for(int i=0;i<numbers.length;++i){
            res+=numbers[i];
        }
        return res;
    }
    boolean cmp(int n1,int n2){
        String s1 = n1+""+n2;
        String s2 = n2+""+n1;
        for(int i=0;i<s1.length();++i){
            if(s1.charAt(i)>s2.charAt(i))return true;
            else if(s1.charAt(i)<s2.charAt(i)) return false;
        }
        return true;
        //使用Integer.parseInt()可能会溢出
        //return Integer.parseInt(s1)>Integer.parseInt(s2);
    }
}

方法二：使用快速排序。其是方法一的改进，采用了快排，因此时间复杂度比方法一要好。

public class Solution {
    public String PrintMinNumber(int [] numbers) {
        quicksort(0,numbers.length-1,numbers);
        String res = "";
        for(int i=0;i<numbers.length;++i){
            res+=numbers[i];
        }
        return res;
    }
    void quicksort(int low,int high,int numbers[]){
        if(low<high){
            int mid = partion(low,high,numbers);
            quicksort(low,mid-1,numbers);
            quicksort(mid+1,high,numbers);
        }
    }
    int partion(int low,int high,int numbers[]){
        int pivot = numbers[low];
        while(low<high){
            while(low<high&&cmp(numbers[high],pivot))--high;
            numbers[low] = numbers[high];
            while(low<high&&cmp(pivot,numbers[low]))++low;
            numbers[high] = numbers[low];
            numbers[low] = pivot;
        }
        return low;
    }
    boolean cmp(int n1,int n2){
        String s1 = n1+""+n2;
        String s2 = n2+""+n1;
        for(int i=0;i<s1.length();++i){
            if(s1.charAt(i)>s2.charAt(i))return true;
            else if(s1.charAt(i)<s2.charAt(i)) return false;
        }
        return true;
        //使用Integer.parseInt()可能会溢出
        //return Integer.parseInt(s1)>Integer.parseInt(s2);
    }
}