0

我正在尝试在 Swift 中实现 TimSort。我已经提到了这两个链接：这个和这个 我已经转换为 Swift 的代码是：

import UIKit

class ViewController: UIViewController {

var arr : [Int] = []
let run : Int = 5

override func viewDidLoad() {
    super.viewDidLoad()
    for _ in 0..<10 {
        arr.append(Int(arc4random_uniform(100)))
    }
    timSort()
}

override func didReceiveMemoryWarning() {
    super.didReceiveMemoryWarning()
    // Dispose of any resources that can be recreated.
}

func insertionSort(_ array:[Int]) -> [Int] {
    var a = array
    for x in 1..<a.count {
        var y = x
        while y > 0 && a[y] < a[y - 1] {
            a.swapAt(y - 1, y)
            y -= 1
        }
    }
    return a
}

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])
            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 timSort() {
    print("Unsorted : \(arr)")
    for i in stride(from: 0, to: arr.count, by: run) {
        print("i : \(min((i + run),(arr.count)))")
        arr.replaceSubrange(i..<min((i + run),(arr.count)), with: insertionSort(Array(arr[i..<min((i + run),(arr.count))])))
    }
    print("after insertion sort \(arr)")

    var runCount = run
    while runCount < arr.count{
        for x in stride(from: 0, to: arr.count, by: 2 * runCount) {
            print("x : \(x) runcount \(runCount) calc : \(x + 2 * runCount)")
            arr.replaceSubrange(x..<min((x + 2 * runCount),(arr.count)), with: merge(leftPile: Array(arr[x..<(x + runCount)]), rightPile: Array(arr[(x + runCount)..<min((x + 2 * runCount),(arr.count))])))
        }
        runCount = runCount * 2
    }

    print("Sorted : \(arr)")
}
}

我面临的问题是，当我在两个链接中执行代码时，它适用于任何运行值（如run = 7），但我的代码中没有发生同样的情况。

我的代码只有在run = 5和时才能正常工作arr.count = 10。arr.replaceSubrange(x..<min((x + 2 * runCount),(arr.count)), with: merge(leftPile: Array(arr[x..<(x + runCount)]), rightPile: Array(arr[(x + runCount)..<min((x + 2 * runCount),(arr.count))])))在所有其他情况下，它会在这条线上崩溃。

我尝试了各种方法，但无法解决问题。请有人帮我指出来。

4

2 回答 2

3

您还需要进行几项min检查。在您的最后一个while循环中，x + runCount可以超过arr.count，因此x + runCount需要替换为min(x + runCount, arr.count). 通过这些添加min的检查，代码现在可以针对各种大小的run和运行arr.count：

func timSort() {
    print("Unsorted : \(arr)")
    for i in stride(from: 0, to: arr.count, by: run) {
        print("i : \(min((i + run),(arr.count)))")
        arr.replaceSubrange(i..<min((i + run),(arr.count)), with: insertionSort(Array(arr[i..<min((i + run),(arr.count))])))
    }
    print("after insertion sort \(arr)")

    var runCount = run
    while runCount < arr.count{
        for x in stride(from: 0, to: arr.count, by: 2 * runCount) {
            print("x : \(x) runcount \(runCount) calc : \(x + 2 * runCount)")
            arr.replaceSubrange(x..<min(x + 2 * runCount, arr.count), with: merge(leftPile: Array(arr[x..<min(x + runCount, arr.count)]), rightPile: Array(arr[min(x + runCount, arr.count)..<min(x + 2 * runCount, arr.count)])))
        }
        runCount = runCount * 2
    }

    print("Sorted : \(arr)")
}
于 2018-07-27T11:13:35.463 回答
1

从 Swift 5.0 开始，'sort()' 方法使用 timsort 作为其默认实现。你可以在这里找到更多关于它的信息

于 2019-10-05T06:55:09.197 回答