arrays - 如何在 swift 中对数组进行稳定排序？

Question

我一直在使用 sort() 函数，但它混淆了相对顺序。

这就是我的代码的样子。

recipes.sort { $0.skill.value <= $1.skill.value }

Swift API说:

The sorting algorithm is not stable. A nonstable sort may change the relative order of elements that compare equal.

我怎样才能改变它，使相对顺序与以前一样？

Answer 1

下面的实现就像标准库中的sorted方法一样工作，没有额外的限制。

extension RandomAccessCollection {

    /// return a sorted collection
    /// this use a stable sort algorithm
    ///
    /// - Parameter areInIncreasingOrder: return nil when two element are equal
    /// - Returns: the sorted collection
    public func stableSorted(by areInIncreasingOrder: (Element, Element) throws -> Bool) rethrows -> [Element] {

        let sorted = try enumerated().sorted { (one, another) -> Bool in
            if try areInIncreasingOrder(one.element, another.element) {
                return true
            } else {
                return one.offset < another.offset
            }
        }
        return sorted.map { $0.element }
    }
}

稳定排序需要保留原始顺序。所以我们给每个元素一个顺序的权重，除了它的值，索引，然后原来的排序方法就会起作用，因为永远不会有 2 个相等的元素。