java - 执行包含多个列表的扩展合并排序

Question

最近我一直在研究一些数据结构来记录我的日常 Activity 。

我的方法是创建一个类似于树的标签系统。就像“货币”类可以包含“津贴”、“食品和饮料”和“租金”等子类。每个标签可能包含更多子标签，例如“津贴”将包含“年度津贴”、“每月津贴”和“每日津贴”。

每个子标签都将包含对其前后其他子标签的引用(顺便说一句，我在 Java 中这样做，这意味着不允许进行指针算术)，例如“每月津贴”将具有 previousSibling 指向“年度津贴”，nextSibling 指向“每日津贴”。

每个标签还将包含一些记录特定操作的实例(我们称其为“事件”)，例如标签“Allowance”中可能有一个实例记录每年从银行利息收到的金额。

所有这些都很好，我已经对它们进行了编码，但是在显示数据时，我陷入了困境。我想要的是总结特定时间段内的收入和支出，比如从 4 月 21 日到 4 月 22 日。我打算对它们进行排序，然后选出 4 月 21 日至 22 日之间的事件范围。当您只处理单个标签中的事件时，这是可以的。我想要的是收集作为某个指定标签的子标签的所有标签中的所有事件，例如我想收集“Allowance”标签中的所有事件，以及它的 3 个子标签的事件。

我打算用合并排序方法来解决这个排序问题:首先我对“年度津贴”、“每月津贴”和“每日津贴”的事件进行排序。然后我对“津贴”、“食物和饮料”、“租金”进行排序，然后对“货币”进行排序。假设我们对Allowance进行排序，其子项已经排序，我需要做的有点类似于:

ArrayList<Event> list = new ArrayList<>();

//assuming yearlyAllowance.events is an ArrayList<Event>
list.add(yearlyAllowance.events.get(0));
list.add(monthlyAllowance.events.get(0));
list.add(dailyAllowance.events.get(0));
list.add(allowance.events.get(0));

//helper method
sortByTime(list);
ArrayList<Event> finalList = new ArrayList<>();

while(!list.isEmpty()){
  finalList.add(list.get(0));
  Event tmpEvent = list.get(0);
  list.remove(0);
  //slipping the next event in tmpEvent in, should take O(ln(n)) time on average as list is sorted and we're binary inserting them
  if(tmpEvent.nextSibling != null){
    insertBinary(list, tmpEvent.nextSibling);
  }
}

所以在这里，我基本上是同时对几个列表进行合并排序，这意味着在每个阶段，我将一堆已排序的列表合并在一起。我遵循这种方法是因为我可以将每个标签标记为已排序或未排序，这意味着我不必重新排序所有内容，例如如果您只是收集所有内容，则在对货币类进行排序后重新排序津贴标签来自货币标签及其子标签事件的事件并对它们进行排序。

有更好的方法吗？我将其作为 Android 应用程序来执行，因此我确实需要速度才能向用户显示信息。

Answer 1

您不需要对所有事件进行排序，因为您只需要事件间隔。更好的方法是找到指定时间间隔内的事件并将它们添加到列表中然后进行排序。在将事件添加到最终列表之前，您只需要有一个 if 语句。