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

How do I insert an element at the correct position into a sorted array in Swift?(如何将正确位置的元素插入到 Swift 中的排序数组中?)

问题描述

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

NSArray has - (NSUInteger)indexOfObject:(id)obj inSortedRange:(NSRange)r options:(NSBinarySearchingOptions)opts usingComparator:(NSComparator)cmp to determine the insert position of a new object in a sorted array.

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

What is the best and high-performance way to do this in pure 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]

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

Instead of appending the new element and then sorting the array, I would like to figure out the correct position and insert the element:

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

推荐答案

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

Here is a possible implementation in Swift using binary search (from http://rosettacode.org/wiki/Binary_search#Swift with slight modifications):

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: 一样，假设数组相对于比较器进行排序.如果元素已经存在于数组，或在保留顺序的同时可以插入的索引.这对应NSArray方法的NSBinarySearchingInsertionIndex.

As with indexOfObject:inSortedRange:options:usingComparator: it is assumed that the array is sorted with respect to the comparator. It returns either (any) index of the element if the element is already present in the array, or the index where it can be inserted while preserving the order. This corresponds to the NSBinarySearchingInsertionIndex of the NSArray method.

用法:

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

这篇关于如何将正确位置的元素插入到 Swift 中的排序数组中?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持编程学习网！