如何在Swift中将正确位置的元素插入到排序数组中？

Question

NSArray必须- (NSUInteger)indexOfObject:(id)obj inSortedRange:(NSRange)r options:(NSBinarySearchingOptions)opts usingComparator:(NSComparator)cmp确定排序数组中新对象的插入位置.

在纯Swift中执行此操作的最佳和高性能方法是什么？

有点像:

var myArray = ["b", "e", "d", "a"]
myArray.sort { $0 < $1 }

// myArray is now [a, b, d, e]

myArray.append("c")
myArray.sort { $0 < $1 }

// myArray is now [a, b, c, d, e]

我想找出正确的位置并插入元素,而不是追加新元素然后对数组进行排序:

let index = [... how to calculate this index ??? ...]
myArray.insert("c", atIndex: index)

Answer 1

这是Swift中使用二进制搜索的一种可能的实现方式(来自 http://rosettacode.org/wiki/Binary_search#Swift稍作修改):

extension Array {
    func insertionIndexOf(elem: Element, isOrderedBefore: (Element, Element) -> Bool) -> Int {
        var lo = 0
        var hi = self.count - 1
        while lo <= hi {
            let mid = (lo + hi)/2
            if isOrderedBefore(self[mid], elem) {
                lo = mid + 1
            } else if isOrderedBefore(elem, self[mid]) {
                hi = mid - 1
            } else {
                return mid // found at position mid
            }
        }
        return lo // not found, would be inserted at position lo
    }
}

与indexOfObject:inSortedRange:options:usingComparator:此一样,假设阵列相对于比较器进行排序.如果元素已存在于数组中,则返回元素的(任意)索引,或者在保留顺序时返回可插入元素的索引.这对应于NSBinarySearchingInsertionIndex该NSArray方法.

用法:

let newElement = "c"
let index = myArray.insertionIndexOf(newElement) { $0 < $1 } // Or: myArray.indexOf(c, <)
myArray.insert(newElement, atIndex: index)

Answer 2

在swift 3中你可以使用index(where:):

var myArray = ["a", "b", "d", "e"]
let newElement = "c"
if let index = myArray.index(where: { $0 > newElement }) {
    myArray.insert(newElement, at: index)
}

请注意,在这种情况下,您需要反转闭包内的条件(即,>而不是<增加数组中的元素),因为您感兴趣的索引是第一个与谓词不匹配的元素.此外,nil如果新插入的元素将成为数组中的最后一个,则此方法将返回(newElement = "z"在上面的示例中).

为方便起见,这可以包装到一个单独的函数来处理所有这些问题:

extension Collection {
    func insertionIndex(of element: Self.Iterator.Element,
                        using areInIncreasingOrder: (Self.Iterator.Element, Self.Iterator.Element) -> Bool) -> Index {
        return index(where: { !areInIncreasingOrder($0, element) }) ?? endIndex
    }
}

用法:

var myArray = ["a", "b", "d", "e"]
let newElement = "c"
let index = myArray.insertionIndex(of: newElement, using: <)
myArray.insert(newElement, at: index)

Answer 3

根据WWDC 2018 Session 406: Swift Generics (Expanded)，可以通过对集合对象进行切片，以更高效、更通用的方式执行二分查找。

有两个相当大的好处Slice：

1. 切片始终是原始对象的子集，无需分配额外的内存。
2. 切片的所有索引都指向原始对象。
   例如，如果你片5个对象的数组let slice = array[2..<4]然后slice.startIndex是2不0。

RandomAccessCollection是一个协议（继承自BidirectionalCollection），各种结构/类都遵守

extension RandomAccessCollection where Element : Comparable {
    func insertionIndex(of value: Element) -> Index {
        var slice : SubSequence = self[...]

        while !slice.isEmpty {
            let middle = slice.index(slice.startIndex, offsetBy: slice.count / 2)
            if value < slice[middle] {
                slice = slice[..<middle]
            } else {
                slice = slice[index(after: middle)...]
            }
        }
        return slice.startIndex
    }
}

例子：

let array = [1, 2, 4, 7, 8]
let index = array.insertionIndex(of: 6) // 3

您可以扩展函数以检查谓词闭包而不是单个值

extension RandomAccessCollection { // the predicate version is not required to conform to Comparable
    func insertionIndex(for predicate: (Element) -> Bool) -> Index {
        var slice : SubSequence = self[...]

        while !slice.isEmpty {
            let middle = slice.index(slice.startIndex, offsetBy: slice.count / 2)
            if predicate(slice[middle]) {
                slice = slice[index(after: middle)...]
            } else {
                slice = slice[..<middle]
            }
        }
        return slice.startIndex
    }
}

例子：

struct Person { let name : String }

let array = [Person(name: "Adam"), Person(name: "Cynthia"), Person(name: "Nancy"), Person(name: "Tom")]
let index = array.insertionIndex{ $0.name < "Bruce" } // 1

Answer 4

如果您知道您的数组已排序,则可以使用此方法 - 它将适用于任何类型的数组.它每次都会遍历整个数组,因此不要将它与大型数组一起使用 - 如果您有更大的需求,请选择其他数据类型!

func insertSorted<T: Comparable>(inout seq: [T], newItem item: T) {
    let index = seq.reduce(0) { $1 < item ? $0 + 1 : $0 }
    seq.insert(item, atIndex: index)
}

var arr = [2, 4, 6, 8]
insertSorted(&arr, newItem: 5)
insertSorted(&arr, newItem: 3)
insertSorted(&arr, newItem: -3)
insertSorted(&arr, newItem: 11)
// [-3, 2, 3, 4, 5, 6, 8, 11]

Answer 5

在@vadian和@Martin R 的答案的基础上，我注意到一些细微的差异，主要是插入索引与集合中等效元素的索引不匹配，或者与等效元素序列的第一个索引不匹配。

例如：

• 如果您想查找5in的插入索引[4, 5, 6]，则会返回索引2，如果您只想搜索该值，这可能会出现问题。
• 在 中[5, 5, 5]，再次搜索5返回索引1，该索引不是第一个插入索引。

这与 NSArray 的实现及其各种选项的行为不匹配，因此这里是另一个尝试考虑到这一点的解决方案：

extension RandomAccessCollection {
    /// Get the index of or an insertion index for a new element in
    /// a sorted collection in ascending order.
    /// - Parameter value: The element to insert into the array.
    /// - Returns: The index suitable for inserting the new element
    ///            into the array, or the first index of an existing element.
    @inlinable
    public func sortedInsertionIndex(
        of element: Element
    ) -> Index where Element: Comparable {
        sortedInsertionIndex(of: element, by: <)
    }
    
    /// Get the index of or an insertion index for a new element in
    /// a sorted collection that matches the rule defined by the predicate.
    /// - Parameters:
    ///   - value: The element to insert into the array.
    ///   - areInIncreasingOrder:
    ///       A closure that determines if the first element should
    ///       come before the second element. For instance: `<`.
    /// - Returns: The index suitable for inserting the new element
    ///            into the array, or the first index of an existing element.
    @inlinable
    public func sortedInsertionIndex(
         of element: Element,
         by areInIncreasingOrder: (Element, Element) throws -> Bool
    ) rethrows -> Index {
        try sortedInsertionIndex { try areInIncreasingOrder($0, element) }
    }
    
    /// Get the index of or an insertion index for a new element in
    /// a sorted collection that matches the rule defined by the predicate.
    ///
    /// This variation is useful when comparing an element that
    /// is of a different type than those already in the array.
    /// - Parameter isOrderedAfter:
    ///     Return `true` if the new element should come after the one
    ///     provided in the closure, or `false` otherwise. For instance
    ///     `{ $0 < newElement }` to sort elements in increasing order.
    /// - Returns: The index suitable for inserting the new element into
    ///            the array, or the first index of an existing element.
    @inlinable
    public func sortedInsertionIndex(
         where isOrderedAfter: (Element) throws -> Bool
    ) rethrows -> Index {
        var slice: SubSequence = self[...]

        while !slice.isEmpty {
            let middle = slice.index(slice.startIndex, offsetBy: slice.count/2)
            if try isOrderedAfter(slice[middle]) {
                slice = slice[index(after: middle)...]
            } else {
                slice = slice[..<middle]
            }
        }
        return slice.startIndex
    }
}

由于有时您不关心插入索引，而是关心与给定元素匹配的第一个或最后一个索引，因此以下是上述内容的变体也满足这些要求：

extension RandomAccessCollection {
    @inlinable
    public func sortedFirstIndex(
        of element: Element
    ) -> Index? where Element: Comparable {
        sortedFirstIndex(of: element, by: <)
    }
    
    @inlinable
    public func sortedFirstIndex(
         of element: Element,
         by areInIncreasingOrder: (Element, Element) throws -> Bool
    ) rethrows -> Index? where Element: Comparable {
        let insertionIndex = try sortedInsertionIndex(of: element, by: areInIncreasingOrder)
        guard insertionIndex < endIndex, self[insertionIndex] == element else { return nil }
        return insertionIndex
    }
    
    @inlinable
    public func sortedLastIndex(
        of element: Element
    ) -> Index? where Element: Comparable {
        sortedLastIndex(of: element, by: <)
    }
    
    @inlinable
    public func sortedLastIndex(
        of element: Element,
        by areInIncreasingOrder: (Element, Element) throws -> Bool
    ) rethrows -> Index? where Element: Comparable {
        let insertionIndex = try sortedInsertionIndex(of: element) { try areInIncreasingOrder($1, $0) }
        let finalIndex = index(insertionIndex, offsetBy: -1)
        guard finalIndex >= startIndex, self[finalIndex] == element else { return nil }
        return finalIndex
    }
}