Java - 列出<Integer>排序,比较器和溢出

Question

我有以下代码按降序对列表进行排序

List<Integer> list=Arrays.asList(Integer.MAX_VALUE, -1);
list.sort((x, y) -> y-x);
System.out.println(list)

结果是

[-1, 2147483647]

现在,我知道我不应该写yx因为它可能导致溢出问题.

但问题是为什么输出呢？我相信,输出会[2147483647, -1]因为-1 - Integer.MAX_VALUEIS -2147483648,仍然是一个负整数,广告的操作似乎没有溢出问题的影响.我做错了什么？

Answer 1

正如您可以在页面底部附近的Oracle的Object Ordening Java教程中阅读的那样：

您可能会想用以下更简单的方法替换Comparator中的最终return语句：

return e1.number() - e2.number(); 

除非您完全确定没有人会有负号的员工，否则请不要这样做！该技巧通常不起作用，因为有符号整数类型不足以表示两个任意有符号整数的差。如果i是一个大的正整数，而j是一个大的负整数，则i-j将溢出并返回一个负整数。生成的比较器违反了我们一直在谈论的四个技术限制（传递性）之一，并产生了可怕的，微妙的错误。这不是纯粹的理论问题；人们被它烧死了。

此处描述的情况是OP遇到的情况：两个整数之间的差大于Integer.MAX_VALUE，因此在比较期间将溢出，从而导致意外的排序。

Answer 2

我只是按照@Robin Topper 所说的做了。

import java.util.*;
public class Test {
    public static void main(String... args) {
        List<Integer> list = Arrays.asList(Integer.MAX_VALUE, -1);
        list.sort((x, y) -> {
            System.out.println("x: " + x + " y: " + y);
            System.out.println("y - x = " + (y - x));
            return y - x;
        });
        System.out.println(list);
    }
}

我得到了

x: -1 y: 2147483647
y - x = -2147483648
[-1, 2147483647]

我们可以看到

List#sort(Comparator)Comparator以相反的顺序将值应用到给定的值。

1. 给定Comparator,
2. 当它与-1和 一起应用时2147483647，
3. (y - x)( 2147483647 - -1) 部分溢出，为负数-2147483648，
4. 确实-1小于2147483647。

这是源代码。

列表#排序（比较器）

@SuppressWarnings({"unchecked", "rawtypes"})
default void More ...sort(Comparator<? super E> c) {
    Object[] a = this.toArray();
    Arrays.sort(a, (Comparator) c);
    ListIterator<E> i = this.listIterator();
    for (Object e : a) {
        i.next();
         i.set((E) e);
    }
}

数组#排序（比较器）

public static void sort(int[] a) {
    DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
}

DualPovotQuicksort#sort()