Swift：计算合并排序中的交换

Question

我正在尝试计算合并排序中的交换。看似很直白的命题，但是我的逻辑好像有问题

这是我尝试增加计数的代码的相关部分：

    while leftIndex < leftPile.count && rightIndex < rightPile.count {
        if leftPile[leftIndex] < rightPile[rightIndex] {
            // nothing swapped here
            orderedPile.append(leftPile[leftIndex])
            leftIndex += 1
        } else if leftPile[leftIndex] > rightPile[rightIndex] {
            orderedPile.append(rightPile[rightIndex])
            // item taken from right pile == swapped -> increment swapCount
            swapCount += 1
            rightIndex += 1
        } else {
            orderedPile.append(leftPile[leftIndex])
            leftIndex += 1
            // item taken from left pile == swapped -> increment swapCount
            swapCount += 1
            orderedPile.append(rightPile[rightIndex])
            rightIndex += 1
        }
    }

出于某种原因，我用以下数组计算了 5 次交换：

unsortedArray = [2, 1, 3, 1, 2]
sortedArray = [1, 1, 2, 2, 3]
swapCount = 5

这是我的完整 class:

class MergeSortWithCounter {

    var swapCount: Int64

    init() {
        swapCount = 0
    }

    func mergeSort<T: Comparable>(_ array: [T]) -> [T] {
        guard array.count > 1 else { return array }
        let middleIndex = array.count / 2
        let leftArray = mergeSort(Array(array[0..<middleIndex]))
        let rightArray = mergeSort(Array(array[middleIndex..<array.count]))
        return merge(leftPile: leftArray, rightPile: rightArray)
    }

    func merge<T: Comparable>(leftPile: [T], rightPile: [T]) -> [T] {

        var leftIndex = 0
        var rightIndex = 0
        var orderedPile = [T]()
        if orderedPile.capacity < leftPile.count + rightPile.count {
            orderedPile.reserveCapacity(leftPile.count + rightPile.count)
        }

        while leftIndex < leftPile.count && rightIndex < rightPile.count {
            if leftPile[leftIndex] < rightPile[rightIndex] {
                // nothing swapped here
                orderedPile.append(leftPile[leftIndex])
                leftIndex += 1
            } else if leftPile[leftIndex] > rightPile[rightIndex] {
                orderedPile.append(rightPile[rightIndex])
                // item taken from right pile == swapped -> increment swapCount
                swapCount += 1
                rightIndex += 1
            } else {
                orderedPile.append(leftPile[leftIndex])
                leftIndex += 1
                // item taken from left pile == swapped -> increment swapCount
                swapCount += 1
                orderedPile.append(rightPile[rightIndex])
                rightIndex += 1
            }
        }

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

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

        return orderedPile
    }
}

我知道我遗漏了一些非常简单的东西，但我花了比我愿意承认的更多的时间来找出我的错误所在。

感谢阅读！

Answer 1

当您不必：

        if leftPile[leftIndex] < rightPile[rightIndex] {
            // nothing swapped here

你的意思是

        if leftPile[leftIndex] <= rightPile[rightIndex] {
            // nothing swapped here

Swift：计算合并排序中的交换

Swift: Counting Swaps in a merge sort

mergesort

swift