快速排序是一種基于分治技術(shù)的重要排序算法。不像歸并排序是按照元素在數(shù)組中的位置對(duì)它們進(jìn)行劃分，快速排序按照元素的值對(duì)它們進(jìn)行劃分。具體來(lái)說(shuō)，它對(duì)給定數(shù)組中的元素進(jìn)行重新排列，以得到一個(gè)快速排序的分區(qū)。在一個(gè)分區(qū)中，所有在s下標(biāo)之前的元素都小于等于A[s]，所有在s下標(biāo)之后的元素都大于等于A[s]。

顯然，建立了一個(gè)分區(qū)以后，A[s]已經(jīng)位于它在有序數(shù)組中的最終位置，接下來(lái)我們可以繼續(xù)對(duì)A[s]前和A[s]后的子數(shù)組分別進(jìn)行排序（使用同樣的方法）。
為了排序一個(gè)數(shù)組A的全部元素，初始調(diào)用的是QUICKSORT(A,1，A.length)。

下面的算法對(duì)A[p..r]進(jìn)行分區(qū)（先偽代碼一下、領(lǐng)會(huì)意思）。

PARTITION(A,p,r)  x = A[r]  i = p - 1  for j = p to r - 1   if A[j] ≤ x    i = i + 1    exchange A[i] with A[j]  exchange A[i+1] with A[r]  return i+1

快速排序算法的效率：

在最優(yōu)情況下，鍵值比較的次數(shù)Cbest(n)滿足下面的遞推式：

當(dāng)n>1時(shí)，Cbest(n)=2Cbest(n/2)+n，Cbest(1)=0

根據(jù)主定理，Cbest(n)∈Θ(nlogn)；對(duì)于n=2k的情況求得Cbest(n) = nlog(n)。

在最差的情況下，所有的分裂點(diǎn)都趨于極端：兩個(gè)子數(shù)組有一個(gè)為空，而另一個(gè)子數(shù)組僅僅比被分區(qū)的數(shù)組少一個(gè)元素。具體來(lái)說(shuō)，這種令人遺憾的情況會(huì)發(fā)生在升序的數(shù)組上，也就是說(shuō)輸入的數(shù)組已經(jīng)被排過(guò)序了。所以，在進(jìn)行了n+1次比較之后建立了分區(qū)，并且將A[0]和它本身進(jìn)行了交換以后，快速排序算法還會(huì)對(duì)嚴(yán)格遞增的數(shù)組A[1..n-1]進(jìn)行排序。對(duì)規(guī)模減小了的嚴(yán)格遞增數(shù)組的排序會(huì)一直繼續(xù)到最后一個(gè)子數(shù)組A[n-2..n-1]。這種情況下，鍵值比較的總次數(shù)應(yīng)該等于：

Cworst(n)=(n+1)+n+...+3=(n+1)(n+2)/2-3∈Θ(n2)

現(xiàn)在，輪到討論快速排序在平均情況下的效率了。對(duì)于大小為n的隨機(jī)排列的數(shù)組，快速排序的平均鍵值比較次數(shù)記為Cavg(n)。假設(shè)分區(qū)的分裂點(diǎn)s（0≤s≤n-1)位于每個(gè)位置的概率都是1/n，我們得到下面的遞推關(guān)系式：

Cavg(0)=0，Cavg(1)=0

Cavg(n)≈2nlnn≈1.38nlogn
因此，快速排序在平均情況下，僅比最優(yōu)情況多執(zhí)行38%的比較操作。此外，它的最內(nèi)層循環(huán)效率非常高，使得在處理隨機(jī)排列的數(shù)組時(shí)，速度要比歸并排序快。

以下是快速排序的Go代碼：