前面兩種算法面臨的問題，桶排序浪費(fèi)存儲空間，冒泡排序增加了時間的復(fù)雜度，那怎樣才能既節(jié)省時間、又節(jié)省存儲空間呢！

下面要講到快速排序

舉個例子

假設(shè)我們要將 6，1，2，7，9，3，4，5，10，8 這個數(shù)列按照從小到大的順序進(jìn)行排列。

從初始序列中找到一個數(shù)做為基準(zhǔn)數(shù)，為了方便操作，這里我們選第一個數(shù) 6 作為基準(zhǔn)數(shù)。先從右往左找一個小于 6 的數(shù)，再從左往右找一個大于 6 的數(shù)，然后交換它們。這里可以用兩個變量 i 和 j，分別指向序列最左邊和最右邊。剛開始的時候讓 i 指向序列的最左邊(即 i=1)，指向數(shù)字 6。讓 j 指向序列的最右邊(即 j=10)，指向數(shù)字 8。

page25image3826848.png

接下來，因為當(dāng)前指針 i 指向的數(shù)字是基準(zhǔn)數(shù)，所以我們先利用指針 j 從右往左找到一個小于 6 的數(shù)，再利用指針 i 從左往右找到一個大于 6 的數(shù)，然后交換這兩個數(shù)的位置。

比如，在本文中，當(dāng)前指針 j 指向的數(shù)字是 8，8 大于 6，繼續(xù)向左移動指針 j，直到指針 j 指向數(shù)字 5 的時候停下。

現(xiàn)在開始讓 i 往右移動指針， 當(dāng)指針 i 指向數(shù)字7的時候停下

接下來最關(guān)鍵的一步是交換 7 和 5 的位置

[圖片上傳中...(page25image3844320.png-dbf60e-1516352429167-0)]

page25image3844320.png

第一次交換結(jié)束后，我們繼續(xù)向左移動指針 j ，到 4 的位置停下。然后向右移動指針 i ，到9的位置停下，交換 i 和 j 的位置

page26image3832896.png

page26image3828640.png

現(xiàn)在我們完成了第二次交換，繼續(xù)左移動指針 j 發(fā)現(xiàn) 3 小于6， 停下來。接著向右移動指針 i 發(fā)現(xiàn)此時 指針 i 和指針 j 在3處相遇，這意味著我們的第一輪位移操作即將結(jié)束

page27image3845888.png

然后將基準(zhǔn)數(shù)6和3互相交換位置， 此時的6前面的數(shù)都小于6， 6后面的數(shù)字都大于6。到此時，我們第一輪的操作已經(jīng)完成。

page27image3843872.png

page27image3845440.png

接下來非常重要的一步是以6的分界點(diǎn)將數(shù)列一分為二，將左邊和右邊的數(shù)列分別執(zhí)行上面的步驟。直到數(shù)列中的每一個數(shù)字都?xì)w位。

page29image3884864.png

swift 代碼實現(xiàn)

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)
}

參考文獻(xiàn) 《啊哈！算法》