使用合并排序计算反转，Swift

Question

我在使用 Swift 计算倒数时遇到问题。我花了 45 分钟，45 分钟后 Xcode 崩溃了。我从来没有得到答案。你能帮我弄清楚问题是什么吗？因为这个问题只花了人们几秒钟的时间。这些代码有什么问题？顺便说一句，问题是计算数组中的反转（100000 个未排序的整数）

import UIKit
var count: Int = Int()


func mergeSort(_ array: [Int]) -> [Int] {
    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(leftPile: [Int], rightPile: [Int]) -> [Int] {

    var leftIndex = 0
    var rightIndex = 0



    var orderedPile = [Int]()


    while leftIndex < leftPile.count && rightIndex < rightPile.count {
        if leftPile[leftIndex] < rightPile[rightIndex] {
            orderedPile.append(leftPile[leftIndex])
            leftIndex += 1
        } else if leftPile[leftIndex] > rightPile[rightIndex] {
            orderedPile.append(rightPile[rightIndex])
            count += leftPile.count - leftIndex
            rightIndex += 1

        } else {
            orderedPile.append(leftPile[leftIndex])
            leftIndex += 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

}

func ready(fileName: String) -> [Int] {
    guard let path = Bundle.main.path(forResource: fileName, ofType: "txt") else {
        return [Int]()
    }

    do {
        let numbers = try String(contentsOfFile: path).components(separatedBy: "\r\n")
            .flatMap {Int([=11=])}
        mergeSort(numbers)




        return numbers
    } catch {
        return [Int]()
    }
}
ready(fileName: "IntegerArray"))
print(count)

Answer 1

我认为您的实施有一些问题阻碍了进展。我在操场上重建了你的项目，并将你的代码与以下代码进行了比较，我认为这是一种更 "classical" 的算法实现方式：

func mergeAlt(leftPile: [Int], rightPile: [Int]) -> [Int] {

    var leftPileCopy = leftPile
    var rightPileCopy = rightPile

    var orderedPile = [Int]()

    while !leftPileCopy.isEmpty && !rightPileCopy.isEmpty {
        if leftPileCopy.first! <= rightPileCopy.first! {
            orderedPile.append(leftPileCopy.first!)
            leftPileCopy.removeFirst()
        } else {
            orderedPile.append(rightPileCopy.first!)
            rightPileCopy.removeFirst()
        }
    }

    // By this stage, only one array will have anything in it
    while !leftPileCopy.isEmpty {
        orderedPile.append(leftPileCopy.first!)
        leftPileCopy.removeFirst()
    }

    while !rightPileCopy.isEmpty {
        orderedPile.append(rightPileCopy.first!)
        rightPileCopy.removeFirst()
    }
    return orderedPile
}

您会注意到这里的主要区别在于此实现比较每个数组中的第一项，然后删除较小的一项，从而逐渐减小数组的大小。我认为您的方法是使用索引跟踪每个数组中的位置，这是导致延迟的原因。

例如，我运行在操场上反对你在 1000 运行dom 数字的数组上的实现。你的算法运行s 代码的 "compare" 部分（即 "if leftPile[index] < rightPile[index]..."）每堆几乎 8000 次，然后运行s 处理剩余代码的代码（即section starting "while leftIndex < leftPile.count...") 每堆超过 1000 次。以上实现运行s 500次用于对比测试然后4次处理任何残留元素

你能运行将这个用于更大的阵列吗？如果有帮助请告诉我？

Answer 2

好的。解决了。不要使用 playground 来运行这个。打开一个 x-code 项目大约需要 1 秒。

Answer 3

以防有人在这里试图找到基于归并排序

的计数倒置Swift 4 版本

import Foundation

func sortAndCount(_ array : [Int]) -> ([Int], Int) {
    guard array.count > 1 else {
        return (array, 0)
    }

    let middleIndex = array.count / 2
    let (leftArray, leftCount)  = sortAndCount(Array(array[0..<middleIndex]))
    let (rightArray, rightCount) = sortAndCount(Array(array[middleIndex..<array.count]))
    let (finalArray, splitCount) = mergeAndCountSplitInversation(leftArray, rightArray)
    return (finalArray, leftCount + rightCount + splitCount)
}

func mergeAndCountSplitInversation(_ leftPile: [Int], _ rightPile: [Int]) -> ([Int], Int) {
    var leftIndex = 0
    var rightIndex = 0
    var orderedPile = [Int]()
    var inversationCount = 0

    while leftIndex < leftPile.count && rightIndex < rightPile.count {
        if leftPile[leftIndex] <= rightPile[rightIndex] {
            orderedPile.append(leftPile[leftIndex])
            leftIndex += 1
        } else {
            orderedPile.append(rightPile[rightIndex])
            rightIndex += 1
            inversationCount = inversationCount + leftPile.count - leftIndex
        }
    }

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

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

    print("inversion for array - \(orderedPile)")
    print("count - \(inversationCount)")
    return (orderedPile, inversationCount)
}

func inverstionCountNaive (_ array :[Int]) -> Int {
    var inverstionCount = 0
    for i in 0..<array.count-1 {
        for j in i+1..<array.count {
            if array[i] > array[j] {
              inverstionCount += 1
            }
        }
    }

    return inverstionCount
}

let array = [2, 1, 3, 1, 2]

print("origin - \(array)")
print("sorted - \(sortAndCount(array))")
print("naive approuch count - \(inverstionCountNaive(array))")

使用合并排序计算反转，Swift

Counting Inversions with merge sort, Swift

sorting

merge

counting

swift