剑指 Offer 45. 把数组排成最小的数--排序

剑指 Offer 45. 把数组排成最小的数--排序

自定义快排 + compare内置函数（内置函数主要解决了整型越界的问题）

自定义：两个数字字符串连接，将结果更大的组合前面的数字表示更大。关于大小的传递性不做证明

class Solution {
    public String minNumber(int[] nums) {
        String[] strs = new String[nums.length];
        for(int i = 0;i < nums.length;i++){
            strs[i] = String.valueOf(nums[i]);
        }
        quicksort(strs,0,strs.length - 1);
        StringBuilder sb = new StringBuilder();
        for(String str : strs){
            sb.append(str);
        }
        return sb.toString();
    }

    public void quicksort(String[] arr,int low,int high){
        if(low < high){
            int index = partition(arr,low,high);
            quicksort(arr,index + 1,high);
            quicksort(arr,low,index - 1);
        }
    }
    public int partition(String[] arr,int low,int high){
        int i = low;
        int j = high;
        String x = arr[i];
        while(i < j){
            while(i < j && (arr[j] + x).compareTo(x + arr[j]) >= 0){
                j--;
            }
            if(i < j) arr[i] = arr[j];
            while(i < j && (x + arr[i]).compareTo(arr[i] + x) >= 0){
                i++;
            }
            if(i < j)arr[j] = arr[i];
        }
        arr[i] = x;
        return i;   
    }
  
}