快速排序.md

快速排序是通过一个值，一个指针从左到右找出大于基数的值，一个指针从右到左找出小于基数的值，之后交换位置。当两个指针到大同一个位置，交换基数和查找中间位置。

快速排序图解

第一次快排，8作为中间值

左侧大于8第一个是12 右侧小于8是1 12和1交换位置

指针继续查找则已经错过，将基数和刚才查找最后最小值交换，8和1互换

第二次快排前面1 3 6基数为1

大于1第一个数是3小于1 小于1没有，则保持不变

第三次快排基数8后面的12

因为只有一个元素，则不需要排序

第四次排序基数1右边大集合3和6 基数为3

查找大于3第一个数是6，查找小于3没有，则保持不变

第四次排序基数3右边大集合6 基数为6

因为只有一个元素，则保持不变

到底排序完成

示例代码

class Solution {
    func quickSort(_ numbers:inout [Int]) {
        quickSubSort(&numbers, 0, (numbers.count - 1))
    }
    func quickSubSort(_ numbers:inout [Int], _ start:Int, _ end:Int) {
        let lenght = end - start + 1
        guard lenght > 1 else {
            return
        }
        var leftIndex:Int = start + 1
        var rightIndex:Int = end
        var numberIndex = start
        let number = numbers[numberIndex]
        while true {
            guard leftIndex <= end, rightIndex >= start else {
                break
            }
            var minIndex:Int?
            var maxIndex:Int?
            for i in ((start + 1) ... rightIndex).reversed() {
                if numbers[i] < number {
                    minIndex = i
                    break
                }
            }
            guard let _minIndex = minIndex else {
                break
            }
            for j in (leftIndex ... end) {
                if numbers[j] >= number {
                    maxIndex = j
                    break
                }
            }
            if let _maxIndex = maxIndex, _maxIndex < _minIndex {
                self.swap(&numbers, _minIndex, _maxIndex)
            } else {
                self.swap(&numbers, start, _minIndex)
                numberIndex = _minIndex
                break
            }
            leftIndex += 1
            rightIndex -= 1
        }
        quickSubSort(&numbers, start, numberIndex - 1)
        quickSubSort(&numbers, (numberIndex + 1), end)
    }
    func swap(_ numbers:inout [Int], _ left:Int, _ right:Int) {
        guard numbers.count > 2, left != right, numbers.count > left, numbers.count > right else {
            return
        }
        let temp = numbers[left]
        numbers[left] = numbers[right]
        numbers[right] = temp
    }
}