如何在swift中稳定排序数组？

I've been using the sort() function but it mixes up the relative order.

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

This is how my code looks.

这就是我的代码看起来的样子。

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

Swift API says that:

Swift API说:

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

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

How can I change this so that the relative order stays the same as before?

如何更改此值以使相对顺序与以前保持一致?

4 个解决方案

#1

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

Took from here: https://medium.com/@cocotutch/a-swift-sorting-problem-e0ebfc4e46d4

从这里开始:https://medium.com/@cocotutch/a-swift-sorting-problem-e0ebfc4e46d4

#2

The implementation below just work like the sorted method in the standard library, without additional limit.

下面的实现就像标准库中的排序方法一样,没有额外的限制。

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: (Iterator.Element, Iterator.Element) -> Bool?) -> [Iterator.Element] {

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

A stable sort needs to preserve the original order. So we give every element a weight of order besides its value, the index, then the original sort method will just work, as there will never be 2 equal elements.

稳定的排序需要保留原始订单。因此,除了它的值,索引之外,我们给每个元素一个权重,然后原始的排序方法将起作用,因为永远不会有2个相等的元素。

#3

I appreciate the elegance of leavez's answer. I adapted it to have the same signature as Sequence.sorted(by:):

我很欣赏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 }
  }
}

#4

I use this wrapper

我用这个包装器

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