如何在Swift中将正确位置的元素插入到已sorting的数组中？
NSArray有- (NSUInteger)indexOfObject:(id)obj inSortedRange:(NSRange)r options:(NSBinarySearchingOptions)opts usingComparator:(NSComparator)cmp来确定一个新的对象在sorting数组中的插入位置。
在纯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]
而不是追加新的元素，然后sorting数组，我想找出正确的位置，并插入元素：
let index = [... how to calculate this index ??? ...] myArray.insert("c", atIndex: index)
下面是使用二进制searchSwift中的一个可能的实现（ 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:假设数组是按照比较器sorting的。 如果元素已经存在于数组中，它将返回（任何）元素的索引，或者可以在保存顺序的同时插入它的索引。 这对应于NSArray方法的NSBinarySearchingInsertionIndex 。
用法：
let newElement = "c" let index = myArray.insertionIndexOf(newElement) { $0 < $1 } // Or: myArray.indexOf(c, <) myArray.insert(newElement, atIndex: index)
如果你知道你的数组是sorting的，你可以使用这个方法 – 它可以处理任何types的数组。 它每次都会遍历整个数组，所以不要在大数组中使用这个数组 – 如果有更大的需求，可以使用另一种数据types！
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]
二叉search树是要走的路。
在有序数组上，取中间的元素，看看该位置的对象是否大于新对象。 这样，你可以用一个单一的比较来忘记数组元素的一半。
重复这一步与剩下的一半。 再次，通过一个比较，你可以忘记剩下的一半。 目标元素数量现在是数组大小的四分之一，只有两个比较。
重复该操作，直到find插入新元素的正确位置。
这是一个关于二叉search树与swift的好文章
在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)
