时间戳

首页 > 解决方案 > Java 如何使用有逻辑缺陷的比较器正确排序这个 ArrayList？

java - Java 如何使用有逻辑缺陷的比较器正确排序这个 ArrayList？

问题描述

在处理作业时，我发现对于以下代码，Java 对我的 ArrayList 点进行了正确排序（给定比较器中的条件），在 SlopeOrder 比较方法中使用或不使用第二个 if 语句。当 Java 被告知只要 a > b 两点相等时，它怎么可能正确地对这些点进行排序？

public class Point implements Comparable<Point>
{
   ...

   public Comparator<Point> slopeOrder() 
   {
       return new SlopeOrder();
   }

   private class SlopeOrder implements Comparator<Point> 
   {
      public int compare(Point o1, Point o2) 
      {
         double a = slopeTo(o1);
         double b = slopeTo(o2);
         if (a < b) return -1;
         if (a > b) return +1; // <--- Can be removed and list will still be sorted correctly
         return 0;
      }
   }

   ...

   public static void main(String[] args)
   {
      ArrayList<Point> points = new ArrayList<Point>();

      points.add(new Point(1,1));
      points.add(new Point(4,6));
      points.add(new Point(6,6));
      points.add(new Point(3,9));
      points.add(new Point(0,0));
      points.add(new Point(5,2));

      Point origin = new Point(0,0);
      Collections.sort(points, origin.slopeOrder());
      System.out.println(points);
   }
}

注意：slopeTo 只是将给定点（在本例中为原点）的斜率返回到坐标平面上的某个其他点

输出：

[(0, 0), (5, 2), (1, 1), (6, 6), (4, 6), (3, 9)]

标签： javacomparatorcomparable

解决方案

这是一个巧合。

我试着在你的列表中放 100 个随机点。排序列表中的前十几个或更多排序正确，但是在 (1, 9) 之后，(0, 3) 开始了一个新的排序序列，有 (4, 0), (7, 1) 等。整个排序list 仅包含 4 个子序列，每个子序列都已正确排序。

这是一个有趣的结果。

您有缺陷的比较器在某些不应该返回的情况下返回 0。0 使这些元素保持原来的顺序。因此，它本身并不能保证错误的排序顺序。

我使用了 Oracle jdk-11.0.3。

推荐阅读