将数字排列成最大数 - 算法证明

有众所周知的算法问题 http://www.programcreek.com/2014/02/leetcode-largest-number-java/，给定数字数组，例如[1, 20, 3, 14]在这种情况下，以尽可能形成最大数字的方式排列数字320141.

SO 和其他网站上有很多解决方案，使用以下算法：

String[] strs = new String[nums.length];
for(int i=0; i<nums.length; i++){
    strs[i] = String.valueOf(nums[i]);
}

Arrays.sort(strs, new Comparator<String>(){
    public int compare(String s1, String s2){
        String leftRight = s1+s2;
        String rightLeft = s2+s1;
        return -leftRight.compareTo(rightLeft);

    }
});

StringBuilder sb = new StringBuilder();
for(String s: strs){
    sb.append(s);
}

return sb.toString();

它当然有效，但我找不到该算法的正式证明。有一个答案quora http://qr.ae/RgAefL，但我不会称其为正式证明。

有人可以给我一份证明草图或参考一些书籍或文章吗？如何从最初的问题得到这个解决方案？

PS我试图解决原来的问题，但我的解决方案是错误的，我无法得到正确的结果，现在我无法完全理解解决方案。

关于符号：我将使用管道来分隔数字，所以它是 更容易看到数字的顺序和结果数在 同时：3|20|14|1

让我们暂时假设这种关系——我们称之为R代表为<=运算符——由比较定义 函数是全序。由表达式决定

-(a+b).compareTo(b+a)

直观地说，如果我们有两个数字a and b and b|a是 比大a|b, b应该获得比a，即它应该 出现在左侧a在解决方案中。如果a|b大于b|a，这是另一种方式 圆形的。如果a|b = b|a，顺序无关紧要。

需要注意的一件重要事情是，这种关系不仅影响两个 数字a and b孤立地考虑但也告诉我们一些事情 关于结果数字，两个数字被嵌入：

If a<=b, then x|a|b|y <= x|b|a|y

with x and y是数量 任意长度。换句话说：如果我们有一个数字序列 我们交换两个相邻的数字a and b with a<=b， 所结果的 之后数字将大于或等于。

例子：3|14|20|1 因为14

我们现在可以假设解决方案不是唯一的 我们的关系暗示R矛盾：我们假设 解决方案是一些不符合的特定顺序R. Since R是一个 总顺序，我们可以重新排列数字以匹配R通过交换 相邻元素直到顺序符合R。这种重新排序可以 与冒泡排序进行比较。然而，在每次交换操作中 引导我们到新的顺序，结果数字增加！这是 显然是矛盾的，所以原来的顺序不可能是 解决方案。

剩下要展示的是R是全序，即 传递性、反对称性和完全性。既然你要的是草图 证明，我将省略这部分。最重要的部分是证明 传递性，即

a and b 暗示一个.