gpt4 book ai didi

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

转载 作者:行者123 更新时间:2023-11-28 06:25:00 25 4
gpt4 key购买 nike

我正在尝试计算合并排序中的交换。这似乎是一个非常简单的命题,但我的逻辑似乎有问题。

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

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

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

感谢阅读!

最佳答案

当您不需要时,您正在交换相同的情况:

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

你的意思是

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

关于Swift:计算合并排序中的交换,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/42190680/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com