Fork me on GitHub

【译】Swift算法俱乐部-有序数组

本文是对 Swift Algorithm Club 翻译的一篇文章。
Swift Algorithm Clubraywenderlich.com网站出品的用Swift实现算法和数据结构的开源项目,目前在GitHub上有18000+⭐️,我初略统计了一下,大概有一百左右个的算法和数据结构,基本上常见的都包含了,是iOSer学习算法和数据结构不错的资源。
🐙andyRon/swift-algorithm-club-cn是我对Swift Algorithm Club,边学习边翻译的项目。由于能力有限,如发现错误或翻译不妥,请指正,欢迎pull request。也欢迎有兴趣、有时间的小伙伴一起参与翻译和学习🤓。当然也欢迎加⭐️,🤩🤩🤩🤨🤪。
本文的翻译原文和代码可以查看🐙swift-algorithm-club-cn/Ordered Array


有序数组(Ordered Array)

这是一个始终从低到高排序的数组。 每当您向此数组添加新元素时,它都会插入到其排序位置。

当您希望对数据进行排序并且相对较少地插入新元素时,有序数组非常有用。在这种情况下,它比排序整个数组更快。但是,如果您需要经常更改数组,则使用常规数组并手动对其进行排序可能会更快。

实现是非常基础的。 它只是Swift内置数组的包装器:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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()函数。 这是对它的初步尝试:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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中测试:

1
2
3
4
5
6
7
8
9
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()函数有点慢。 在最坏的情况下,它需要扫描整个数组。 我们可以通过使用二分搜索查找插入点来加快速度。

新的版本:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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排序数组对应的文章解释了优势和权衡。

作者:Matthijs Hollemans
翻译:Andy Ron
校对:Andy Ron

坚持原创技术分享,您的支持将鼓励我继续创作!