如何在 Swift 中将正确位置的元素插入到已排序的数组中? [英] How do I insert an element at the correct position into a sorted array in 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 中将正确位置的元素插入到已排序的数组中?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！