我的快速快速排序实现有什么问题？

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

您的递归调用不正确