快速排序

快排序的基本思想

快排序(Quick Sort)是一种分治的排序算法。

• 首先从待排序对象中选出一个基准对象(Pivot)， 通常取第一个对象;
• 然后调整所有待排序对象，将基准对象放置到某个特定的位置，使基准对象左边的所有对象的关键字都小于等于基准对象的关键字，使基准对象右边的所有对象的关键字都大于等于基准对象的关键字；
• 最后把基准对象左边的那些对象与基准对象右边的那些对象分别看做两个独立的序列，再对这两个序列分别(递归调用快排序算法)排序。

extension Array where Element: Comparable {
    mutating func partition(left: Index, right: Index) -> Index {
        var i = left + 1
        var j = right
        let pivot = self[left]
        while true {
            // scan right
            while left < j {
                if self[j] > pivot {
                    j -= 1
                } else {
                    break
                }
            }
            
            // scan left
            while i < right {
                if self[i] < pivot {
                    i += 1
                } else {
                    break
                }
            }
            
            if i >= j {
                break
            }
            exchange(i, j: j)
        }
        exchange(left, j: j)
        return j
    }
    mutating func quickSort() {
        quickSort(left: 0, right: count - 1)
    }
    mutating func quickSort(left: Index, right: Index) {
        if left >= right {
            return
        }
        let partitionIndex = partition(left: left, right: right)
        quickSort(left: left, right: partitionIndex - 1)
        quickSort(left: partitionIndex + 1, right: right)
    }
}