排序算法三：快速排序

前面两种算法面临的问题，桶排序浪费存储空间，冒泡排序增加了时间的复杂度，那怎样才能既节省时间、又节省存储空间呢！

下面要讲到快速排序

举个例子

假设我们要将 6，1，2，7，9，3，4，5，10，8 这个数列按照从小到大的顺序进行排列。

从初始序列中找到一个数做为基准数，为了方便操作，这里我们选第一个数 6 作为基准数。先从右往左找一个小于 6 的数，再从左往右找一个大于 6 的数，然后交换它们。这里可以用两个变量 i 和 j，分别指向序列最左边和最右边。刚开始的时候让 i 指向序列的最左边(即 i=1)，指向数字 6。让 j 指向序列的最右边(即 j=10)，指向数字 8。

page25image3826848.png

接下来，因为当前指针 i 指向的数字是基准数，所以我们先利用指针 j 从右往左找到一个小于 6 的数，再利用指针 i 从左往右找到一个大于 6 的数，然后交换这两个数的位置。

比如，在本文中，当前指针 j 指向的数字是 8，8 大于 6，继续向左移动指针 j，直到指针 j 指向数字 5 的时候停下。

现在开始让 i 往右移动指针， 当指针 i 指向数字7的时候停下

接下来最关键的一步是交换 7 和 5 的位置

[图片上传中...(page25image3844320.png-dbf60e-1516352429167-0)] page25image3844320.png

第一次交换结束后，我们继续向左移动指针 j ，到 4 的位置停下。然后向右移动指针 i ，到9的位置停下，交换 i 和 j 的位置

page26image3832896.png page26image3828640.png

现在我们完成了第二次交换，继续左移动指针 j 发现 3 小于6， 停下来。接着向右移动指针 i 发现此时 指针 i 和指针 j 在3处相遇，这意味着我们的第一轮位移操作即将结束

page27image3845888.png

然后将基准数6和3互相交换位置， 此时的6前面的数都小于6， 6后面的数字都大于6。到此时，我们第一轮的操作已经完成。

page27image3843872.png page27image3845440.png

接下来非常重要的一步是以6的分界点将数列一分为二，将左边和右边的数列分别执行上面的步骤。直到数列中的每一个数字都归位。

page29image3884864.png

swift 代码实现

func quickSort(_ array: inout [Int], left: Int, right: Int) {
    
    var i, j, pivot: Int
    
    if left > right {
        return
    }
    
    i = left
    j = right
    
    pivot = array[left]
    
    while i != j {
        
        while array[j] >= pivot && i < j {
            j -= 1
        }
        
        while array[i] <= pivot && i < j {
            i += 1
        }
        
        if i < j {
            array.swapAt(i, j)
        }
    }
    
    array[left] = array[i]
    array[i] = pivot
    
    quickSort(&array, left: left, right: i-1)
    quickSort(&array, left: i+1, right: right)
}

参考文献 《啊哈！算法》