美文网首页iOS程序猿iOS学习笔记
【译】Swift算法俱乐部-有序数组

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

作者: Andy_Ron | 来源:发表于2018-12-27 10:52 被阅读9次
    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内置数组的包装器:

    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排序数组对应的文章解释了优势和权衡。

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

    相关文章

      网友评论

        本文标题:【译】Swift算法俱乐部-有序数组

        本文链接:https://www.haomeiwen.com/subject/xzxflqtx.html