快速排序的排序效率在同為O(N*logN)的幾種排序方法中效率較高，因此經(jīng)常被采用。

快速排序的基本思想是：通過一次將需要排序的數(shù)據(jù)分為兩部分，一部分是的數(shù)都比另一部分的數(shù)大，再按這種方法對這兩部分數(shù)據(jù)分別在用快速排序的方法，整個排序過程可以遞歸進行，使整個數(shù)據(jù)變成有序序列。（這里看不懂，不急）

快速排序是C.R.A.Hoare于1962年提出的一種劃分交換排序。它采用了一種分治的策略，通常稱其為分治法(Divide-and-ConquerMethod)。為了方便理解，將快速排序的思想簡化成挖坑填坑+分治。

下面以一個數(shù)組a[10]為例：

首先我們需要先選取一個X(基準數(shù))，這個基準數(shù)我們可以選取數(shù)組的第一個元素或者最后一個元素，也可以選取中間的元素。這里我們選取第一個元素a[0]，同時設(shè)頭(i=0),尾(j=9),然后把a[0]賦值給X，這里就相當于在a[0]的位置挖了一個坑??，這時候我們要從后往前(j--)找一個比X小或者等于X的數(shù)，然后把找到的這個數(shù)挖出來填到我們之前挖的坑里面，當j=8時，符合條件，把a[8]賦值給a[0]，并且i++，這時候我們填上了一個坑，又出現(xiàn)了另一個坑a[8],這時我們需要從前往后(i++)去找一個比X大的數(shù)去填這個坑??，當i=3時，符合條件，把a[3]挖出來賦值給a[8]，并且j--。

在重復上面的操作，先從后往前找一個比X小或者等于的數(shù)，然后把這個數(shù)挖出來去填坑，在從前往后找一個比X大的數(shù)去填坑....

從后往前：當j=5時，符合條件，a[3]=a[5],i++;

從后往前：當i=5時，由于i==j退出，這時a[5]是我們需要填的坑

此時，i=j=5，我們只需要把X這個數(shù)填到a[5]這個坑??里面即可。

從上面的圖片我們可以看出，在a[5]左邊的數(shù)都是比它小或者等于它的數(shù)，右邊的數(shù)都是比它大的數(shù)，這時候我們就完成了一次排序，緊接著我們在對a[0]--a[4]和a[6]--a[9]分別再次重復上述步驟。

這里以a[0]--a[4]為例：設(shè)基準數(shù)X=49（隨便哪個都行），i=0,j=4

對挖坑填數(shù)進行總結(jié):

1．i 為頭; j 為尾; 將基準數(shù)X挖出形成第一個坑a[i]。

2．j--由后向前找比它小的數(shù)，找到后挖出此數(shù)填前一個坑a[i]中。

3．i++由前向后找比它大的數(shù)，找到后也挖出此數(shù)填到前一個坑a[j]中。

4．再重復執(zhí)行2，3二步，直到i==j，最后將基準數(shù)填入a[i]中。

根據(jù)上面的思路

我們先來寫挖坑填坑的代碼：

然后通過遞歸來實現(xiàn)分治：

把上面兩部分合起來得到快速排序的代碼：

有的書上是以中間的數(shù)作為基準數(shù)的，這樣實現(xiàn)也非常方便，直接將中間的數(shù)和第一個數(shù)進行交換就可以了。Swap(s[l], s[(l + r) / 2])

快速排序只是使用數(shù)組原本的空間進行排序，所以所占用的空間應該是常量級的，但是由于每次劃分之后是遞歸調(diào)用，所以遞歸調(diào)用在運行的過程中會消耗一定的空間，在一般情況下的空間復雜度為 O(logn)，在最差的情況下，若每次只完成了一個元素，那么空間復雜度為 O(n)。所以我們一般認為快速排序的空間復雜度為 O(logn)。

最后我們來驗證下代碼：

沒問題，下機，結(jié)束。。。。。。。。。。