给定一组具有2个值的对象。按照第一个值进行排序，然后再按照第二个值进行排序。

Question

Eg.:

{2,3},{1,2},(2,2},{3,1},{2,1} to {1,2},{2,1},{2,2},{2,3},{3,1}

这是我的想法：

对值的第一列进行归并排序。遍历集合以查看第一列中是否有任何重复值。如果有，将它们排队到列表上。

在第二列上对此列表进行归并排序，然后将它们整合到主集合中。虽然似乎可行，但这似乎过于复杂。这应该在 O(NlogN) 中运行，因此如果有人能想到一个更快/相同复杂度的算法，也要发布出来！

谢谢！

- user183037

Answer 1

只需实现一个Comparator<T>，通过首先比较第一个字段，然后如果第一个字段相等则继续比较第二个字段来比较您类型的任何两个对象。然后将集合复制到列表中，调用Collections.sort并将列表和您的比较器传递给它。无需自己实现排序。

比较器应该是这样的：

public class TwoFieldComparator implements Comparator<Foo>
{
    public int compare(Foo first, Foo second)
    {
        // TODO: null checks
        int firstComparison = Integer.compare(first.x, second.x);
        return firstComparison != 0 ? firstComparison
                                    : Integer.compare(first.y, second.y);
    }
}

或者，您可以以同样的方式使您的类实现Comparable<T>。

（提示：这是一个关于Java编程语言中如何实现对象比较的建议）

- Jon Skeet

---

我希望我能够帮忙，但这是一个面试问题，他们希望你自己完成排序。 - user183037

@user183037：如果你一开始就这么说就好了。不过我仍然会使用这种方法，因为它是最通用的方法（适用于任何你想要比较的内容），并且也可以与任何排序算法一起使用——例如，如果你想使用快速排序，这种方法也可以很好地工作。 - Jon Skeet

@Jon Skeet - 对不起，我没有明确提到它，但是它被标记了，我认为那已经足够了...下次我会记得清楚地提到它。正如你所说，我们可以在自己的排序算法中轻松使用这个比较器，而不仅仅是Collections.sort() - 出于某种原因，我没有想到这一点...我一直使用Collections.sort()和一个比较器。我将其标记为答案，因为它是最通用的。再次感谢您的解决方案，非常感激。 - user183037

@user183037：它被标记为“面试”-但不需要自己编写排序部分。这是缺失的重要部分-如果我在问一个面试问题，我通常会期望现有的库可用。无论如何，很高兴能帮到你。 - Jon Skeet

Answer 2

你需要做的是对第二列进行稳定排序，然后再次对第一列进行排序。如果可以确定数字范围，则可以通过某些线性排序方法实现O(N)。

编辑：以“归并排序”为例（因为它是稳定的）：
1、对第二列运行归并排序，然后数字对将根据第二列的值排列。
2、再次对第一列运行归并排序，数字对将按第一列值的顺序排列。但是，由于排序方法是稳定的，这意味着如果第一个数字相同，第二个数字也将被排序(我们在第一次排序中已经做过了)。
因此，num对数组现在是有序的。不需要更多操作。归并排序是O(NlogN)，因此2*O(NlogN)仍然是O(NlogN)。

编辑2：
好吧，我可能让这个问题变得复杂了。即使需要自己实现排序方法，只要确定了数据结构，就可以在自制排序方法的相应部分中填充Jon Skeet编写的比较代码，这可能是最方便的方法。

- RollingBoy

---

编辑：我认为那可能会起作用，那将是一个非常简单的解决方案。 - user183037

Answer 3

正如您在其中一条评论中提到的那样，这是一道面试题。John Skeet的解决方案表明，您不必担心项目中有两个值 - 只需实现正确的比较器即可。

假设您在2011年被问到这个问题，了解您的排序将如何使用是很好的。根据将使用此排序的环境，您可以考虑并行处理（使用多个线程）。这可能会影响您选择的排序算法。

- Arnost Valicek