快速排序（以下簡(jiǎn)稱快排）是一種經(jīng)典的排序算法，名字乍一看非常實(shí)在，細(xì)思之下卻又帶著點(diǎn)不可一世的狂傲。別的排序算法像什么插入排序、選擇排序、歸并排序等等，它們的名字其實(shí)都是在自解釋?zhuān)瑹o(wú)非是在告訴別人我到底是怎么排的。然而快排卻說(shuō)，我很快，所以我叫快速排序。

你只要記住，我很快.jpg

好，在下認(rèn)輸。

當(dāng)然，快排很快，這是真的，在實(shí)踐中可以做到比歸并排序快3倍以上（需要一定的優(yōu)化）。快排的基本思想其實(shí)很簡(jiǎn)單，就是交換 + 分治，可以看作是對(duì)冒泡排序的一種改進(jìn)。具體的我就不啰嗦了，相信大家對(duì)這個(gè)也非常熟悉了，實(shí)在不了解的同學(xué)可以先Google一下。我直接上Swift的代碼好了（對(duì)我就是喜歡Swift），注釋也寫(xiě)得很清楚：

//最壞情況(初始數(shù)組順序或逆序): 
//T(n) = T(0) + T(n-1) + θ(n) = θ(1) + T(n-1) + θ(n) = T(n-1) + θ(n) = θ(n2)(等差級(jí)數(shù))
//一般情況: T(n) = θ(nlgn)
func quickSort(inout list: [Int], startIndex: Int, endIndex: Int) {
    //若startIndex＜endIndex則序列至少有2個(gè)元素，其余情況(只有1個(gè)或0個(gè))不需要排序直接返回
    guard startIndex < endIndex else {
        return
    }
    //排序，并返回參考點(diǎn)(參考點(diǎn)左側(cè)的數(shù)都小于參考點(diǎn)，右側(cè)的都大于參考點(diǎn))
    let referenceIndex = divide(&list, startIndex: startIndex, endIndex: EndIndex)
    //遞歸，對(duì)參考點(diǎn)左邊部分排序
    quickSort(&list, startIndex: startIndex, endIndex: referenceIndex - 1)
    //遞歸，對(duì)參考點(diǎn)右邊部分排序
    quickSort(&list, startIndex: referenceIndex + 1, endIndex: endIndex)
}

上面的代碼已經(jīng)實(shí)現(xiàn)了快排的整體過(guò)程，但是divide這個(gè)函數(shù)還沒(méi)有定義，下面就來(lái)實(shí)現(xiàn)它：

func divide(inout list: [Int], startIndex: Int, EndIndex: Int) -> Int {
    //用來(lái)記錄參考點(diǎn)位置(遍歷完成之后用來(lái)放置序列的第一個(gè)數(shù))
    var referenceIndex = startIndex
    //參考點(diǎn)的值(序列中第一個(gè)元素)
    let referencePoint = list[startIndex]
    //遍歷序列，與參考點(diǎn)比較
    for compareIndex in startIndex+1 ... EndIndex {
        //若小于參考點(diǎn)，就跟referenceIndex后的元素交換，referenceIndex前進(jìn)一位
        if list[compareIndex] < referencePoint {
            (list[referenceIndex+1], list[compareIndex]) = (list[compareIndex], list[referenceIndex+1])
            referenceIndex++
        }
    }
    //將序列第一個(gè)元素放到參考點(diǎn)位置，它左邊的值都比它小，右邊的都比他大
    (list[startIndex], list[referenceIndex]) = (list[referenceIndex], list[startIndex])
    //返回參考點(diǎn)位置
    return referenceIndex
}

這樣整個(gè)過(guò)程就完成了。其實(shí)上面的

if list[compareIndex] < referencePoint { 
    (list[referenceIndex+1], list[compareIndex]) = (list[compareIndex], list[referenceIndex+1]) 
    referenceIndex++ 
}

可以改為:

if list[compareIndex] < referencePoint {
    (list[referenceIndex], list[compareIndex]) = (list[compareIndex], list[++referenceIndex])
}

少了一行代碼，但是不太好理解，有點(diǎn)得不償失，所以還是算了。現(xiàn)在測(cè)試一下：

//測(cè)試數(shù)組
var testList = [3, 8, 9, 10, 2, 1]
quickSort(&testList, startIndex: 0, EndIndex: testList.count - 1)

var testList2 = [28, 3, 76, 99, 42, 111, 88, 99, 75]
quickSort(&testList2, startIndex: 0, EndIndex: testList2.count - 1)

嗯，親測(cè)有效。

開(kāi)頭的代碼注釋上我寫(xiě)了快排的時(shí)間復(fù)雜度分析，在最壞情況下其實(shí)效率很低，跟冒泡選擇那些『慢速』排序差不多，都是θ(n2)。造成這種情況的原因是，如果每次選擇的參考點(diǎn)都是最小或者最大的那個(gè)，那么所謂的分治就失去了意義，因?yàn)槊看伪闅v完序列都是把參考點(diǎn)單獨(dú)拎出，然后剩下的數(shù)據(jù)歸為一組（都比參考點(diǎn)大或者小），在過(guò)程中會(huì)出現(xiàn)n組序列，每組都要遍歷一遍，效率自然低下。

基于上述思路，有一種很直接的優(yōu)化方法，就是選取參考點(diǎn)的時(shí)候不再使用第一個(gè)元素，而是隨機(jī)選取。這么做了之后，在最壞的情況下時(shí)間復(fù)雜度其實(shí)還是θ(n2)，但最壞情況的出現(xiàn)跟待排序的序列順序已經(jīng)無(wú)關(guān)，而是由于隨機(jī)函數(shù)取值不佳。實(shí)際上，隨機(jī)化快速排序得到理論最壞情況的可能性僅為1/(2^n)。所以隨機(jī)化快速排序可以對(duì)于絕大多數(shù)輸入數(shù)據(jù)達(dá)到θ(nlgn)的期望時(shí)間復(fù)雜度。

要實(shí)現(xiàn)隨機(jī)化快排，只需要在原先的divide函數(shù)開(kāi)頭加上這兩句就行:

//獲得一個(gè)在startIndex和EndIndex之間的隨機(jī)數(shù)
let random = getRandomNumIn(startIndex ... EndIndex)
//將序列的第一個(gè)元素與隨機(jī)參考點(diǎn)進(jìn)行交換
(list[startIndex], list[random]) = (list[random], list[startIndex])

獲取隨機(jī)數(shù)的函數(shù)：

func getRandomNumIn(range: Range<Int>) -> Int {
    guard let min = range.first, let max = range.last else {
        return 0
    }
    let delta = max - min + 1
    //不能直接arc4random % delta，否則在x86、x64不同平臺(tái)運(yùn)行時(shí)由于字長(zhǎng)不同會(huì)出現(xiàn)不可測(cè)錯(cuò)誤
    let randomDelta = Int(arc4random() % UInt32(delta))
    let randomNum = min + randomDelta
    return randomNum
}

對(duì)外提供一個(gè)randomQuickSort函數(shù)：

func randomQuickSort(inout list: [Int], startIndex: Int, EndIndex: Int) {
    guard startIndex < EndIndex else {
        return
    }
    //排序，并返回參考點(diǎn)(參考點(diǎn)左側(cè)的數(shù)都小于參考點(diǎn)，右側(cè)的都大于參考點(diǎn))
    let referenceIndex = randomDivide(&list, startIndex: startIndex, EndIndex: EndIndex)
    //遞歸對(duì)參考點(diǎn)左邊部分排序
    randomQuickSort(&list, startIndex: startIndex, EndIndex: referenceIndex - 1)
    //遞歸對(duì)參考點(diǎn)右邊部分排序
    randomQuickSort(&list, startIndex: referenceIndex + 1, EndIndex: EndIndex)
}

func randomDivide(inout list: [Int], startIndex: Int, EndIndex: Int) -> Int {
    let random = getRandomNumIn(startIndex ... EndIndex)
    (list[startIndex], list[random]) = (list[random], list[startIndex])
    
    return divide(&list, startIndex: startIndex, EndIndex: EndIndex)
}

好了，快排講完了。接下來(lái)講講高階函數(shù)。高階函數(shù)簡(jiǎn)單來(lái)說(shuō)呢，就是函數(shù)可以作為變量、參數(shù)、返回值等等，總之函數(shù)是一等公民。Swift是一個(gè)多范式語(yǔ)言，具有一些函數(shù)式語(yǔ)言的特性，函數(shù)自然便是一等公民。下面我還是以快排代碼為例來(lái)解釋一下。之前我們的quickSort跟divide是兩個(gè)獨(dú)立的函數(shù)，quickSort在內(nèi)部調(diào)用divide函數(shù)的時(shí)候需要傳一堆參數(shù)。而且 divide這個(gè)函數(shù)可能被別的函數(shù)調(diào)用，或者被直接使用，如果傳入的序列跟 quickSort使用的是同一個(gè)的話，序列就有可能被意外地多次改變，不能被正確排序。這種情況下，我們可以把divide定義在quickSort內(nèi)部:

func customQuickSort(inout list: [Int], startIndex: Int, EndIndex: Int) {
    let divide: () -> Int = {
        //用來(lái)記錄參考點(diǎn)位置(遍歷完成之后用來(lái)放置序列的第一個(gè)數(shù))
        var referenceIndex = startIndex
        //參考點(diǎn)的值(序列中第一個(gè)數(shù))
        let referencePoint = list[startIndex]
        //遍歷序列，與參考點(diǎn)比較
        for compareIndex in startIndex+1 ... EndIndex {
            //若小于參考點(diǎn)，就跟referenceIndex后的數(shù)交換，referenceIndex前進(jìn)一位
            if list[compareIndex] < referencePoint {
                (list[referenceIndex], list[compareIndex]) = (list[compareIndex], list[++referenceIndex])
            }
        }
        //將序列第一個(gè)數(shù)放到參考點(diǎn)位置，它左邊的值都比它小，右邊的都比他大
        (list[startIndex], list[referenceIndex]) = (list[referenceIndex], list[startIndex])
        //返回參考點(diǎn)位置
        return referenceIndex
    }
    
    //startIndex==EndIndex表明這一部分已排序完成
    guard startIndex < EndIndex else {
        return
    }
    //排序，并返回參考點(diǎn)(參考點(diǎn)左側(cè)的數(shù)都小于參考點(diǎn)，右側(cè)的都大于參考點(diǎn))
    let referenceIndex = divide()
    //遞歸對(duì)參考點(diǎn)左邊部分排序
    customQuickSort(&list, startIndex: startIndex, EndIndex: referenceIndex - 1)
    //遞歸對(duì)參考點(diǎn)右邊部分排序
    customQuickSort(&list, startIndex: referenceIndex + 1, EndIndex: EndIndex)
}

divide內(nèi)部的代碼跟之前完全一樣，但是它現(xiàn)在是被聲明為一個(gè)局部變量，只能在quickSort內(nèi)部被調(diào)用，而且不需要接受參數(shù)。這個(gè)時(shí)候已經(jīng)不能叫它函數(shù)了，而應(yīng)該叫閉包。閉包簡(jiǎn)單來(lái)講就是一個(gè)帶有上下文環(huán)境的函數(shù)，在這個(gè)例子中，divide可以捕獲外部函數(shù)customQuickSort中的變量。其實(shí)換個(gè)說(shuō)法就是在調(diào)用它的時(shí)候，如果在它自己內(nèi)部找不到某個(gè)變量，它就會(huì)到它外部函數(shù)中去尋找。閉包是一個(gè)引用類(lèi)型，它持有上下文環(huán)境的方式也是通過(guò)引用，搞清楚這個(gè)可以避免很多錯(cuò)誤。

好了，快排有了，但如果有人還想使用隨機(jī)化快排呢，而且他不想用我提供的獲取隨機(jī)數(shù)據(jù)的函數(shù)，而是想要用自己的，那該怎么辦呢？這種情況下，我們稍微改一下customQuickSort，讓它額外接收一個(gè)可空閉包作為參數(shù)，這個(gè)閉包用來(lái)獲取一個(gè)隨機(jī)索引，如果閉包不為空，就在divide中調(diào)用閉包，并將獲取的隨機(jī)索引所在的元素與序列的第一個(gè)元素交換，這樣這個(gè)隨機(jī)元素在接下來(lái)的過(guò)程中將作為參考點(diǎn)使用。稍微修改一下上面的代碼：

func customQuickSort(inout list: [Int], startIndex: Int, EndIndex: Int, randomHandler: ((range: Range<Int>) -> Int)?) {
    let divide: () -> Int = {
        if let getRandom = randomHandler {
            let randomIndex = getRandom(range: startIndex ... EndIndex)
            (list[startIndex], list[randomIndex]) = (list[randomIndex], list[startIndex])
        }
    //剩余代碼不變

調(diào)用：

//基本快排
customQuickSort(&testList2, startIndex: 0, EndIndex: testList2.count - 1, randomHandler: nil)
//隨機(jī)化快排，自己傳入一個(gè)獲取隨機(jī)數(shù)的閉包，我這邊使用了原先定義好的那個(gè)
customQuickSort(&testList2, startIndex: 0, EndIndex: testList2.count - 1) { (range) -> Int in
    return getRandomNumIn(range)
}

這樣一來(lái)，使用起來(lái)就靈活了很多。完整的代碼可以看這里。

注：文中的EndIndex為筆誤，函數(shù)參數(shù)首字母不應(yīng)該大寫(xiě)，改為endIndex。github上的代碼已更新。