【译】Swift算法俱乐部-有序数组
Swift算法俱乐部
本文是对 Swift Algorithm Club 翻译的一篇文章。
Swift Algorithm Club是 raywenderlich.com网站出品的用Swift实现算法和数据结构的开源项目，目前在GitHub上有18000+⭐️，我初略统计了一下，大概有一百左右个的算法和数据结构，基本上常见的都包含了，是iOSer学习算法和数据结构不错的资源。
🐙andyRon/swift-algorithm-club-cn是我对Swift Algorithm Club，边学习边翻译的项目。由于能力有限，如发现错误或翻译不妥，请指正，欢迎pull request。也欢迎有兴趣、有时间的小伙伴一起参与翻译和学习🤓。当然也欢迎加⭐️，🤩🤩🤩🤨🤪。
本文的翻译原文和代码可以查看🐙swift-algorithm-club-cn/Ordered Array
有序数组(Ordered Array)
这是一个始终从低到高排序的数组。 每当您向此数组添加新元素时，它都会插入到其排序位置。
当您希望对数据进行排序并且相对较少地插入新元素时，有序数组非常有用。在这种情况下，它比排序整个数组更快。但是，如果您需要经常更改数组，则使用常规数组并手动对其进行排序可能会更快。
实现是非常基础的。 它只是Swift内置数组的包装器：
public struct OrderedArray<T: Comparable> {
fileprivate var array = [T]()
public init(array: [T]) {
self.array = array.sorted()
}
public var isEmpty: Bool {
return array.isEmpty
}
public var count: Int {
return array.count
}
public subscript(index: Int) -> T {
return array[index]
}
public mutating func removeAtIndex(index: Int) -> T {
return array.remove(at: index)
}
public mutating func removeAll() {
array.removeAll()
}
}
extension OrderedArray: CustomStringConvertible {
public var description: String {
return array.description
}
}
如您所见，所有这些方法只是在内部array变量上调用相应的方法。
剩下的是insert()函数。 这是对它的初步尝试：
public mutating func insert(_ newElement: T) -> Int {
let i = findInsertionPoint(newElement)
array.insert(newElement, at: i)
return i
}
private func findInsertionPoint(_ newElement: T) -> Int {
for i in 0..<array.count {
if newElement <= array[i] {
return i
}
}
return array.count // insert at the end
}
辅助函数findInsertionPoint()只是遍历整个数组，寻找插入新元素的正确位置。
注意：
array.insert(... atIndex: array.count)将新对象添加到数组的末尾，所以如果没有找到合适的插入点，我们可以简单地返回array.count作为索引。
在playground中测试：
var a = OrderedArray<Int>(array: [5, 1, 3, 9, 7, -1])
a // [-1, 1, 3, 5, 7, 9]
a.insert(4) // inserted at index 3
a // [-1, 1, 3, 4, 5, 7, 9]
a.insert(-2) // inserted at index 0
a.insert(10) // inserted at index 8
a // [-2, -1, 1, 3, 4, 5, 7, 9, 10]
数组的内容将始终从低到高排序。
不幸的是，当前的findInsertionPoint()函数有点慢。 在最坏的情况下，它需要扫描整个数组。 我们可以通过使用二分搜索查找插入点来加快速度。
新的版本：
private func findInsertionPoint(_ newElement: T) -> Int {
var startIndex = 0
var endIndex = array.count
while startIndex < endIndex {
let midIndex = startIndex + (endIndex - startIndex) / 2
if array[midIndex] == newElement {
return midIndex
} else if array[midIndex] < newElement {
startIndex = midIndex + 1
} else {
endIndex = midIndex
}
}
return startIndex
}
与常规二分搜索的最大区别在于，当找不到值时，不会返回nil，而是返回元素本身所在的数组索引。 这就是我们插入新对象的地方。
请注意，使用二分搜索不会改变insert()的最坏情况运行时复杂性。二分搜索本身只需要O(log n)时间，但在数组中间插入一个新对象仍然需要移动内存中的所有剩余元素。 总的来说，时间复杂度仍然是O(n)。但实际上这个新版本肯定要快得多，特别是在大型数组上。
更完整的代码可以查看Ole Begemann的排序数组。 对应的文章解释了优势和权衡。
