如何在Swift中对数组进行稳定排序？

Question

我一直在使用sort()函数，但它会打乱相对顺序。

这是我的代码样子。

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

Swift API指出：

排序算法不稳定。非稳定排序可能会改变相等元素的相对顺序。

我该如何更改以使相对顺序保持不变？

- demiculus

---

我本来想评论一下，称这被称为“稳定排序”-但是我看到你已经引用了使用这个短语的文档。既然你遇到了表达你所寻找内容的“技术术语”，为什么还要使用不同、含糊的措辞呢？你要寻找一个稳定排序算法。 - Damien_The_Unbeliever

抱歉，我更改了它。 - demiculus

Swift标准库中没有稳定排序。快速的谷歌搜索显示了一个类似的问题https://dev59.com/Fonca4cB1Zd3GeqP7S0k，其中提供了一些解决方案，还有一个Swift功能请求：https://bugs.swift.org/browse/SR-306和这篇文章：https://airspeedvelocity.net/2016/01/10/writing-a-generic-stable-sort/。 - Martin R

请注意，您应该使用严格不等式：<。 - Justin Meiners

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 }
    }
}

稳定排序需要保持原始顺序。因此，我们为每个元素赋予一个除其值之外的顺序权重，即索引，然后原始的排序方法就可以正常工作，因为永远不会出现两个相同的元素。

- leavez

---

@kelin，你的两个编辑实际上并没有起作用。请撤销或修复它们！谢谢。 - Mackie Messer

警告：代码中似乎存在一个错误（在Tom的答案中已经得到了修正），即只有当areInIncreasingOrder(one.element, another.element)为false时才使用稳定的offset顺序。必须在仅当元素相对于排序areInIncreasingOrder“相等”时，即!areInIncreasingOrder(one.element, another.element) && !areInIncreasingOrder(another.element, one.element)时，才需要使用稳定的偏移量。如果我漏掉了什么并且没有错误，请谅解 - 谢谢！ - Benjohn

Answer 2

我很欣赏leavez的答案的优雅。我将其改编为与Sequence.sorted(by:)相同的签名：

extension Sequence {
  func stableSorted(
    by areInIncreasingOrder: (Element, Element) throws -> Bool)
    rethrows -> [Element]
  {
    return try enumerated()
      .sorted { a, b -> Bool in
        try areInIncreasingOrder(a.element, b.element) ||
          (a.offset < b.offset && !areInIncreasingOrder(b.element, a.element))
      }
      .map { $0.element }
  }
}

- Tom

---

我认为@leavez的答案存在一个错误，而你的答案进行了修正。他们的代码在!areInIncreasingOrder时会回退到offset，但它也应该反转参数来检查是否稳定使用offset，只有当元素相对于areInIncreasingOrder“相等”时才使用。 - Benjohn

Answer 3

let sortedArray = (recipes as NSArray).sortedArray(options: .stable, usingComparator: { (lhs, rhs) -> ComparisonResult in
    let lhs = (lhs as! Recipe)
    let rhs = (rhs as! Recipe)
    if lhs.skill.value == rhs.skill.value {
        return ComparisonResult.orderedSame
    } else if lhs.skill.value < rhs.skill.value {
        return ComparisonResult.orderedAscending
    } else {
        return ComparisonResult.orderedDescending
    }
})

从这里取出：https://medium.com/@cocotutch/a-swift-sorting-problem-e0ebfc4e46d4

- Esqarrouth

---

真的太糟糕了，我们不得不返回 Objective-C。为什么他们会选择一种不稳定的排序作为默认选项呢？他们真的无法预见到这样的问题吗？我可能听起来很疯狂，但是我每天都会选择稳定性而不是性能，至少作为默认选项，更别说唯一的选项了。 - devios1

他们只是假设开发人员知道自己在做什么。这应该是一个合理的假设...... “稳定性”在这里是一个数学术语，不要与其他意义混淆，安全这一概念在此不适用。 - Zsolt Szatmari

Answer 4

在Swift 5中，sort()使用稳定的实现，很快它将正式保证是稳定的。

来自Swift论坛的信息：

...
On the other hand, the actual implementation calls

/// Sorts the elements of this buffer according to `areInIncreasingOrder`,
/// using a stable, adaptive merge sort.
///
/// The adaptive algorithm used is Timsort, modified to perform a straight
/// merge of the elements using a temporary buffer.
@inlinable
public mutating func _stableSortImpl(
    by areInIncreasingOrder: (Element, Element) throws -> Bool
) rethrows { ... }

并且

如果我没记错，sort()目前是稳定的，但还不能保证它是稳定的（也就是说，它是稳定的这一事实目前仅是一项实现细节，未来版本的Swift可能会使用不稳定的算法）。

- kelin

---

我没有看到任何迹象表明它将有一天被保证是稳定的？事实上，你的引用说的正好相反，“Swift 的未来版本可能会发布不稳定的算法”。 - numist

@numist，请阅读论坛链接。 - kelin

Answer 5

我很欣赏Tom的回答的优雅。回想起我的Perl时代，我重新编写了它，使用了ComparisonResult和太空船（<=>）运算符：

extension Sequence {
    func sorted(with comparator: (Element, Element) throws -> ComparisonResult) rethrows -> [Element]
    {
        return try enumerated()
            .sorted { (try comparator($0.element, $1.element) || $0.offset <=> $1.offset) == .orderedAscending }
            .map { $0.element }
    }
}

extension Comparable {
    static func <=> (lhs: Self, rhs: Self) -> ComparisonResult {
        if lhs < rhs { return .orderedAscending }
        if lhs > rhs { return .orderedDescending }
        return .orderedSame
    }
}

extension ComparisonResult {
    static func || (lhs: Self, rhs: @autoclosure () -> Self) -> ComparisonResult {
        if lhs == .orderedSame {
            return rhs()
        }
        return lhs
    }
}

- jjrscott

Answer 6

我使用这个包装器

extension Array where Element: Comparable, Element: AnyObject {
    public func stableSorted() -> [Element] {
        let array = self as NSArray
        let result = array.sortedArray(options: .stable) { (left, right) -> ComparisonResult in
            let left = left as! Element
            let right = right as! Element
            if left < right {
                return ComparisonResult.orderedAscending
            }
            if left > right {
                return ComparisonResult.orderedDescending
            }
            return ComparisonResult.orderedSame
        }
        return result as! [Element]
    }
    public func stableReversed() -> [Element] {
        let array = self as NSArray
        let result = array.sortedArray(options: .stable) { (left, right) -> ComparisonResult in
            let left = left as! Element
            let right = right as! Element
            if left > right {
                return ComparisonResult.orderedAscending
            }
            if left < right {
                return ComparisonResult.orderedDescending
            }
            return ComparisonResult.orderedSame
        }
        return result as! [Element]
    }
}

- Antzi