大数据集排序问题

Question

我有一个二维数组，表示构成矩形的点网格的 x 和 y 坐标。使用的数据集通常非常大。我想对从左上角开始并沿平行对角线移动直到右下角的点进行排序。我使用 Arrays.sort 函数和以下比较器来执行此操作：

public int compare(Object o1, Object o2) {
  double[] a1 = (double[])o1;
  double[] a2 = (double[])o2;

  if (a1[0]+a1[1] > a2[0]+a2[1]) return 1;
  else if (a1[0]+a1[1] < a2[0]+a2[1]) return -1;
  else {
    if (a1[0] > a2[0]) return 1;    
    else if (a1[0] < a2[0]) return -1;
    else return 0;
  }  
}

当每个点的 x 和 y 坐标间隔两位数字时，由于某种原因，代码可以工作，但如果它们间隔，则排序会出现错误仅相差一位数字。

原始订单的示例可以在此处找到： http://www.mediafire.com/?slq73v3zn2zs98l

以及生成的排序列表的示例看起来可以在这里找到： http://www.mediafire.com/?x8f08q0qoof398w

为什么排序不起作用？任何帮助将非常感激！

Answer 1

看看您链接到的图片，我认为您想在 Double.compare() "nofollow noreferrer">该点距左上角的L1距离。

这意味着，给定 2d 点 a 和 b，以及您想要比较的“原点”Origin（在本例中为左上角点） ：

distance_a = Math.abs(Origin.x - a.x) + Math.abs(Origin.y - a.y)
distance_b = Math.abs(Origin.x - b.x) + Math.abs(Origin.y - b.y)
return Double.compare(distance_a,distance_b);

并通过比较这些距离进行排序。您可以将其包装到使用 Double.compare() 的合理比较器中。

更新：在您上次发表评论后，我现在了解了额外的排序标准。在比较双精度数时，您可能需要考虑精度问题（其他人可以为您提供更好的建议） ），但是你想要的东西大致如下：

distance_a = Math.abs(Origin.x - a.x) + Math.abs(Origin.y - a.y)
distance_b = Math.abs(Origin.x - b.x) + Math.abs(Origin.y - b.y)
if distance_a is not equal to distance_b // check how you should perform the comparison
    return Double.compare(distance_a,distance_b);
else
    return Double.compare(a.x,b.x);