java - 根据两个标准对列表进行排序的最佳算法是什么？

Question

我有一个列表，需要根据两个条件对其进行排序。 第一个标准是 Boolean ，比方说 isBig .第二个是 Long , 代表时间戳。

我需要以这种方式对列表的元素进行排序:在 isBig = true 之前，然后是 isBig = false .在这些组中，单个元素应根据其时间戳降序排列。

基本上，我希望结果是这样的:

isBig - 2015/10/29
isBig - 2015/10/28
isBig - 2015/10/27
!isBig - 2015/10/30
!isBig - 2015/10/27
!isBig - 2015/10/26

假设对象是这样的:

public class Item {
    Boolean isBig;
    Long timestamp;
    // ...
}

列表只是List<Item> list .

我发现一种方法是创建三个 for 循环:第一个组成两组:isBig和 !isBig .第二个和第三个用于对其中的元素进行排序。最后，我合并了两个列表。

是否有更有效的算法可以根据两个条件对列表进行排序？

Answer 1

您可以使用检查这两个条件的自定义比较方法直接对列表进行排序。

使用 Collections.sort 方法并传递一个自定义比较器，方法 compare 覆盖到:

 int compare(Item o1, Item o2) {
   if (o1.isBig && !o2.isBig)
     return -1;
   if (!o1.isBig && o2.isBig)
     return 1;
   if (o1.timestamp < o2.timestamp)
     return -1;
   if (o1.timestamp > o2.timestamp)
     return 1;
   return 0;
 }

如果您着迷于性能，您可以使用更复杂的方法将其速度提高几个百分点，但对于包含数百个元素的列表，增益可以忽略不计。

一种优化的比较方法:

int compare(Item o1, Item o2) {
   int bigness = (o2.isBig ? 2 : 0) - (o1.isBig ? 2 : 0);
   long diff = o1.timestamp - o2.timestamp;
   return bigness + (int) Long.signum(diff);
}

它没有条件分支，这意味着它可能比上面的原始版本更快。

这可能是为了提高性能所能做的一切。如果我们对您的数据了解更多(例如，大对象总是比小对象多，或者所有时间戳都是唯一的，或者所有时间戳都来自某个狭窄范围等)，我们可能会提出一些更好的解决方案。但是，当我们假设您的数据是任意的并且没有特定模式时，最好的解决方案是使用标准排序实用程序，如我上面所示。

把列表拆分成两个子列表，分别排序肯定会比较慢。实际上，排序算法很可能会将数据分为两组，然后递归地分为四组，依此类推。但是，除法不会遵循 isBig 标准。如果您想了解更多信息，请阅读如何 quick sort或 merge sort工作。