程序 QUICKSORT（A,p,r）

輸入 A：一個數組 p,r:A的某個子數組的開始索引和末尾索引

結果 子數組A[p,r]中的元素按照非遞減順序排序

步驟：

1.如果p>=r，那么無需執行任何操作即可返回

2.否則，執行如下操作：

A.調用PARTITION(A,p,r)，令q被賦值為PARTITION(A,p,r)的返回值

B.遞歸調用QUICKSORT(A,p,q-1)

C.遞歸調用QUICKSORT(A,q+1,r)

快速排序的關鍵是劃分數組。

以排書本順序為例，選擇集合中最右側的書籍（在位置r上的書籍）作為主元。

任意時刻，每本書被精確地劃分到下面四個組中的一個組中，且這些組均位于位置p到位置r之間，從左到右依次是：

a.組L(左側組）：這些書籍的作者名字按照字母排序出現在主元之前或者跟主元的作者名字一致。

b.組R(右側組）：排在組L之后，這些書籍的作者名字按照字母順序出現在主元之后。

c.組U（未知組）：排在組R之后，這些書籍還沒有檢查，因此不知道它們的作者名字與主元的作者名字相比，排序如何。

d.組P（主元）：排在組U之后，僅僅一本書，即主元。

我們從左到右檢查組U中的書籍，將其與主元比較，并將它移動到組L或組R中，一旦檢查到主元位置處，即終止所有操作，因此，與主元比較的始終是組U中最左側的書籍。

接下來分類討論：

1.如果這個書籍的作者名字按照字母排序位于主元的作者名字之后，那么這本書就成為組R中最右側的書籍。由于這本書原來是組U中最左側的書籍，并且組U緊跟在組R之后，所以只需要將組R和組U之間的分割線向右移動一個位置，而無需移動其余任何書籍

2.如果這個書籍的作者名字按照字母排序位于主元的作者名字之前，或者等于主元的作者名字，那么將這本書置為組L中最右側的書籍。將它與組R中最左側的書籍進行調換，并且將組L和組R之間的分割線向右移動一個位置

一旦判定到主元位置，將它與組R中最左側的書籍進行調換。

為了將劃分書籍的操作轉換成劃分一個子數組A[p......r]的操作，首先我們選擇將A [r]（最右側的書籍）作為主元。隨后自左向右檢查子數組，將每個元素與主元進行比較

具體：

1.子數組A[p......q-1]:對應于組L：每個元素小于或等于主元

2.子數組A[q......u-1]:對應于組R：每個元素均大于主元

3.子數組A[u......r-1]:對應于組U：未知情況

4.元素A[r]對應于組P：該位置上放置著主元

在每一步中，將組U中最左側的元素A[u]和主元進行比較。

具體：

1.如果A[u]比主元大，那么將u自增一來將組R和組U之前的分割線向右移動一個位置。

2.反之，如果A[u]小于等于主元，那么將元素A[q](組R中的最左側元素）和A[u]進行調換，且分別將q和u自增一，相當于將組L和組R之間的分割線以及組R和組U之間的分割線分別向右移動一個位置

由上可寫出PARTITION函數：

程序 PARTITION（A,p,r)

輸入 A：一個數組

p,r:A的某個子數組的開始索引和末尾索引

結果 重排A[p.......r]中的元素以便A[p......q-1]中的元素均小于等于A[q]的值，同時令A[q+1......r]中的元素均大于A[q]的值。將索引q返回給調用者。

步驟

1.令q取p

2.令u從p到r-1依次取值：

如果A[u]<=A[r]，那么交換A[q]和A[u]的后置，再將q自增一

3.交換A[q]和A[r]的值，返回q。