为什么我的简单比较器坏了？

sorting java puzzle

2022-09-02 23:11:37

我有一个类，我已经简化为：

final class Thing {
    private final int value;
    public Thing(int value) {
        this.value = value;
    }
    public int getValue() {
        return value;
    }
    @Override public String toString() {
        return Integer.toString(value);
    }
}

我想对这个东西的数组进行排序。所以我创建了一个简单的复制器：

private static final Comparator<Thing> reverse = new Comparator<Thing>() {
    public int compare(Thing a, Thing b) {
        return a.getValue() - b.getValue();
    }
};

然后，我使用的两个参数形式。Arrays.sort

这适用于我的测试用例，但有时数组以奇怪但可重复的顺序结束，因此完全出错。这怎么可能？

答案 1

整数溢出...或者更准确地说，是下溢。

相反，请进行显式比较：

private static final Comparator<Thing> reverse = new Comparator<Thing>() {
    public int compare(Thing a, Thing b) {
      int av = a.getValue(), bv = b.getValue();
      return (av == bv) ? 0 : ((av < bv) ? -1 : +1);
    }
};

如果您确定差异不会“环绕”，则使用减法是可以的。例如，当相关值被限制为非负值时。

答案 2

不能使用减号创建比较。当绝对差值超过时，您将溢出。Integer.MAX_VALUE

请改用以下算法：

int compareInts( int x, int y ) {
  if ( x < y ) return -1;
  if ( x > y ) return 1;
  return 0;
}

出于这样的目的，我喜欢在库中使用此功能。