基于两个标准对列表进行排序的最佳算法是什么？

Question

我有一个列表,我需要根据两个标准进行排序.第一个标准是a Boolean,比方说isBig.第二个是a 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-cycles:第一个组成两个组: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标准.如果您想了解更多信息,请阅读快速排序或合并排序工作的方式.