排序｜ Leetcode 179

Leetcode 分类刷题 —— 排序类（Sort）

1、题目

Leetcode 179. Largest Number

给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。
注意：输出结果可能非常大，所以你需要返回一个字符串而不是整数。

2、思路

1.为什么可以使用字符串比较：
x拼接y，y拼接x的两个字符串是等长的，等长字符串的比较是按照字符串各个字符从高位向低位逐个比较。
字符串大的整型也更大。数学计算法比字符串比较法性能更高。

2.为什么不使用Arrays#sort方法，而是手写快排：
对 String 进行排序，当排序对象不是 Java 中的基本数据类型时，不会使用快排（考虑排序稳定性问题）。
Arrays.sort() 的底层实现会「元素数量/元素是否大致有序」决定是使用插入排序还是归并排序。

3、 字符串比较的 Java 代码

class Solution {
    public String largestNumber(int[] nums) {
        String[] array = new String[nums.length];
        for (int i = 0; i < nums.length ; i++) {
            array[i] = String.valueOf(nums[i]);
        }
        quickSort(array, 0, nums.length - 1);
        if (array[0].equals("0")) {
            return "0";
        }
        StringBuilder ans = new StringBuilder();
        for (String str : array) {
            ans.append(str);
        }
        return ans.toString();
    }

    private void quickSort(String[] nums, int start, int end) {
        if (start >= end) {
            return;
        }
        String pivot = nums[start];
        int index = start;
        for (int i = start + 1; i <= end; i++) {
            if ((nums[i] + pivot).compareTo(pivot + nums[i]) > 0) {
                index += 1;
                swap(nums, index, i);
            }
        }
        swap(nums, index, start);
        quickSort(nums, start, index - 1);
        quickSort(nums, index + 1, end);
    }

    private void swap(String[] nums, int l, int r) {
        String temp = nums[l];
        nums[l] = nums[r];
        nums[r] = temp;
    }
}

参考文章：
https://leetcode.cn/problems/largest-number/solution/chao-guo-100-java-shou-xie-kuai-pai-by-w-gb2w/