arrays - Swift:使用备用键的合并排序算法

Question

我有一个具有以下属性的对象:名称、相关性、时间戳。

我希望数组中的对象按最相关(“相关性”)和最近(“时间戳”)交错排序。

例如:相关、最近、相关、最近等...

现在，我有一个基于单个键进行排序的解决方案，时间复杂度为 O(n log n)。

这是我在 Swift 中的解决方案:

func mergeSort(array: [Entity]) -> [Entity] {
    guard array.count > 1 else { return array }    // 1

    let middleIndex = array.count / 2              // 2

    let leftArray = mergeSort(Array(array[0..<middleIndex]))             // 3

    let rightArray = mergeSort(Array(array[middleIndex..<array.count]))  // 4

    return merge(leftPile: leftArray, rightPile: rightArray)             // 5
}


    func merge(leftPile leftPile: [Entity], rightPile: [Entity]) -> [Entity] {
    // 1
    var leftIndex = 0
    var rightIndex = 0

    // 2
    var orderedPile = [Entity]()

    // 3
    while leftIndex < leftPile.count && rightIndex < rightPile.count {
            if leftPile[leftIndex].timestamp.isGreaterThanDate(rightPile[rightIndex].timestamp) {
                orderedPile.append(leftPile[leftIndex])
                leftIndex += 1
            } else if leftPile[leftIndex].timestamp.isLessThanDate(rightPile[rightIndex].timestamp) {
                orderedPile.append(rightPile[rightIndex])
                rightIndex += 1
            }
            else{
                orderedPile.append(leftPile[leftIndex])
                leftIndex += 1
                orderedPile.append(rightPile[rightIndex])
                rightIndex += 1
            }
    }

    // 4
    while leftIndex < leftPile.count {
        orderedPile.append(leftPile[leftIndex])
        leftIndex += 1
    }

    while rightIndex < rightPile.count {
        orderedPile.append(rightPile[rightIndex])
        rightIndex += 1
    }

    return orderedPile
}

代码完美地对“最近”数组进行排序，我还可以将键从“时间戳”更改为“相关性”，以将其排序为“最相关”。

但是，我想要如上所述以最短的复杂度进行交错排序。有没有人有好的解决办法？

Answer 1

按相关性排序。

制作一份按最近程度排序的副本。

以交替顺序合并副本，保留合并中副本的字典，并且不再添加它们。

两种排序的时间复杂度为O(n log(n))，合并的时间复杂度为O(n)，O(n log(n)).