3

一直在想这件事——我认为这很简单，但我的几何/代数很垃圾，我不记得在学生时代怎么做这些事情了！

已编辑：我有一个与他们站在一起的人的坐标列表-我需要一种算法来在列表（数组）中从左上角到右下角对人进行排序，第二个标准要求靠近左上角原点的坐标采用凌驾于所有其他人之上——你将如何做到这一点？

代码应显示顺序为：

  1. 汤姆
  2. 哈利
  3. 鲍勃
  4. 戴夫

见下图：

替代文字

4

6 回答 6

8

从您的订单来看，您似乎将 y 位置置于比 x 位置更高的优先级，因此在比较两个人时，这样的事情会起作用：

if (a.y > b.y)
// a is before b
else if (a.x < b.x)
// a is before b
else
// b is before a

编辑更新 此比较仍然适用于您的新标准。Y 位置仍然优先于 X 位置。如果 Y 值相等，则最靠近左上角的点将是 X 值较小的点。如果您想让您的对象成为比较器，将其作为比较器函数实现将允许您执行 ArrayList.sort() ，其中负数表示第一个人在第二个人之前：

public int compareTo(person a, person b) {
    if (a.y == b.y)
       return a.x-b.x
    else
       return b.y-a.y
}

//compareTo(Tom, Harry) == -50 (tom is before harry)
//compareTo(Tom, Bob) == -25 (tom is before bob)
//compareTo(Dave, Bob) == 30 (dave is after bob)
于 2009-05-27T14:51:36.913 回答
2

根据它们与 2D 空间左上角的距离对它们进行排序，在本例中为 (0, 100)。

编辑：

显然，这意味着您将遇到两个人与左上角等距的情况，但他们彼此相距不远。

在这种情况下，您需要指定您希望如何订购这些人。如果你想挑更高的人，你可以先按y坐标排序。同样，您可以选择其他一些标准。

所有其他排序算法都会有相同的问题，即当 2 个项目具有相同的排序键时该怎么办。根据定义，在您提出次要排序标准之前，它们被认为是相同的。

于 2009-05-27T14:52:07.850 回答
1

如果您知道 X 的最大数量级，请按（对于您给定的示例）100 * (100 - Y) + X 排序。

于 2009-05-27T14:52:00.953 回答
1

我会说：

orderValue = x+(100-y)

然后根据“最接近”（根据投影到线 y=100-x 上的距离）到左上角的最小 orderValue 进行排序。

于 2009-05-27T15:04:20.617 回答
0

比较器如下所示：

int d = o2.y - o1.y;
if (d == 0)
    d = o1.x - o2.x;
return d;

这将首先按 Y 排序，然后按 X 排序（对于所有具有相同 Y 的对象）。

[编辑] 固定 Y 排序顺序。

于 2009-05-27T14:52:42.870 回答
-3

也许您可以查看在导航中使用的Haversine 公式来计算两点的接近度。但是，这主要适用于球体上的点。 http://en.wikipedia.org/wiki/Haversine_formula

于 2009-05-27T14:53:54.290 回答