快速排序

quick_sort

• 分类：排序算法
• 数据结构：不定
• 最坏时间复杂度：O(n^2)
• 最优时间复杂度：O(n log n)
• 平均时间复杂度：O(n log n)
• 空间复杂度：依据实现的方式不同而不同

快速排序（英语：Quicksort），又称划分交换排序（partition-exchange sort），简称[快排]，一种排序算法

快速排序使用分治法策略来把一个序列（list）分为两个子序列（sub-lists）。

步骤为：

1. 从数列中挑出一个元素，称为"基准"（pivot），
2. 重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任何一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
3. 递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。

递归到最底部时，数列的大小是零或一，也就是已经排序好了。这个算法一定会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

维基百科

    static func quickSort(array: inout Array<Int>, left: Int, right: Int) {
        if left >= right {
            return
        }
        var i = left
        var j = right
        let key = array[i]
        while i < j {
            while i < j && key < array[j] {
                j = j - 1
            }
            array[i] = array[j]
            while i < j && key >= array[i] {
                i = i + 1
            }
            array[j] = array[i]
        }
        array[i] = key
        quickSort(array: &array, left: left, right: i-1)
        quickSort(array: &array, left: i+1, right: right)
    }

---

不定期更新 不合适的地方 还请指点~ 感激不尽