swift - 在插入期间有效地对数组项进行排序

Question

我有一系列的部分:

struct Section {
    let title: String
    var items: [Item]
}

其中包含项目列表:

struct Item {
    let title: String
}

我想用未知数量的项目填充它，并尽可能高效地对数据进行排序。我从远程源获取数据，并在数据传入时对其进行解析。我不知道发送的数据是否已排序，因此盲目地附加到 Section 列表可能行不通在这里。

我希望数据一进来就显示给用户(批量)，所以我不能等到 fetch 操作结束才进行排序。为了举例起见，假设我通过以下方式获取该部分:

let item = Item(title: "Foo")
let sectionTitle = item.characters.first!
if let section = sections.filter({ $0.title == String(sectionTitle) }) {
  // find
} else {
  // create
}

我最初的想法是，一旦找到正确的 Section，循环遍历 Section 项目直到 sectionItem.title > item.title，然后成为插入点:

var insertionPoint = 0
for (i, val) in array.enumerated() {
    insertionPoint = i
    if val.title > item.title { break }
}

section.items.insert(item, at: insertionPoint)

一旦 Section 有许多 Item 对象，这看起来确实效率低下。有没有更合适的方法？

我唯一的其他想法是跟踪此批处理中触及的 Section 项目，然后在每个结束时运行 section.items.sort()批量操作。

Answer 1

对于每批元素:

1. 将每个项目添加到一个部分的临时数组中。
2. 对每个临时数组进行排序。
3. 将已排序的临时数组与该部分的已排序数组合并。合并两个排序数组是一种非常高效的操作。