题目描述

1. 输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。

解题思路

1. 将数组数字重排为最小的数字连接形式，那么直接遍历数组就可以得到我们想要的结果
2. 那么问题来了怎么重组这个排序呢，按照一般的数字排序，就是两个数比较大小然后交换位置，那么这个组合成字符串的我们可以采用两个数字a和b组合成字符串ab和字符串ba比较这两个字符串的大小来确定他们的位置，如果说ab结果比较小，那就代表不需要交换，如果ba小那就代表需要将数字b挪到a之前进行一次交换
3. 确定了比较方法现在需要确定排序方法，排序有N种方法，归并/堆排/快排/选择/插入/希尔/冒泡等一堆方法，当然快的也就是快排了，时间复杂度O(nlogn)那就这个了
4. 方法和数字的数组快排完全一样，只是将交换的判断条件更改为2中所述的内容即可
5. 最后遍历数组重组为字符串

Java源代码

import java.util.ArrayList;

public class Solution {
    public String PrintMinNumber(int [] numbers) {
        sort(numbers, 0, numbers.length-1);
        String result = "";
        for (int i=0; i<numbers.length; i++) result += String.valueOf(numbers[i]);
        return result;
    }
    
    private static void sort(int[] nums, int lo, int hi) {
        if (hi<=lo) return;
        int j = partion(nums, lo, hi);
        sort(nums, lo, j-1);
        sort(nums, j+1, hi);
    }
    
    private static int partion(int[] nums, int low, int high) {
        int key = nums[low];
        while (low<high) {
            while (low<high && compare(key, nums[high])) high--;
            if (low<high) nums[low] = nums[high];
            while (low<high && compare(nums[low], key)) low++;
            if (low<high) nums[high] = nums[low];
        }
        nums[low] = key;
        return low;
    }
    
    private static boolean compare(int a, int b) {
        String ab = String.valueOf(a) + String.valueOf(b);
        String ba = String.valueOf(b) + String.valueOf(a);
        return ab.compareTo(ba)<=0;
    }
}