如何在Swift中创建QuickSort实现？

Question

我正在学习快速，并且已经实现了ADT的可变排序算法。我只是在努力以某种方式无法工作的快速排序。有人可以告诉我代码的缺陷在哪里吗？

func quickSort(start: Int, end: Int) {
    if (end <= start) { return }
    let pivot = self.srtdArr[end]
    var left = start
    var right = end - 1
    while left < right {
        while ((self.srtdArr[left] <= pivot) && (left < end)) {
            left += 1
        }
        while ((self.srtdArr[right] >= pivot) && (right > start)) {
            right -= 1
        }
        if left < right { self.srtdArr.swapAt(left, right) }
    }
    self.srtdArr.swapAt(left, end)
    quickSort(start: start, end: right)
    quickSort(start: right+1, end: end)
    return
}

坦白说，我已经更改了代码，经常使我的头脑不再正确地绕着问题，这就是为什么我需要新鲜的输入。在调试的同时，我首先注意到有时代码会进入递归循环。我更改了一些迭代器或布尔运算符，现在它确定了，但没有正确退出，我也不知道为什么。

Answer 1

如果您从Java算法开始，然后将其转换为Swift https://www.baeldung.com/java-quicksort，会更好。>

Swift版本应该看起来像这样：

func quickSort(_ arr: inout [Int], begin: Int, end: Int) {
    if begin < end {
        let partitionIndex = partition(&arr, begin: begin, end: end)
        quickSort(&arr, begin: begin, end: partitionIndex - 1)
        quickSort(&arr, begin: partitionIndex + 1, end: end)
    }
}
func partition(_ arr: inout [Int], begin: Int, end: Int) -> Int {
    let pivot = arr[end]
    var i = begin - 1
    for j in begin..<end {
        if arr[j] <= pivot {
            i += 1
            arr.swapAt(i, j)
        }
    }
    arr.swapAt(i + 1, end)
    return i + 1
}
如果您想对集合使用quickSort一个可变的通用方法，以与任何Comparable Element一起使用，则该方法：

extension MutableCollection where Self: RandomAccessCollection, Element: Comparable, Index == Int {
    mutating func quickSort(begin: Int, end: Int) {
        if begin < end {
            let partitionIndex = partition(begin: begin, end: end)
            quickSort(begin: begin, end: partitionIndex - 1)
            quickSort(begin: partitionIndex + 1, end: end)
        }
    }
    mutating func partition(begin: Int, end: Int) -> Int {
        let pivot = self[end]
        var i = begin - 1
        for j in begin..<end where self[j] <= pivot {
            i += 1
            swapAt(i, j)
        }
        swapAt(i + 1, end)
        return i + 1
    }
}
游乐场测试：

var array = [1,3,2,5,4,7,6]
array.quickSort(begin: 0, end: 6)
array  // [1, 2, 3, 4, 5, 6, 7]

Answer 2

您的递归调用不正确