標籤：

從快速排序看循環不變數

04-21

原文鏈接：從快速排序看循環不變數 in wangzhike.github.io

1. 基本思路

大概三年前我第一次知道有個快速排序演算法，當時才接觸分治思想不久，加上直接是參考國內一些博客的文章，雖然寫出了可以正確運行的快排程序，但始終覺得有點霧裡看花，無法把握演算法的基本思想，這也導致一段時間過後，我在徒手寫快排程序，腦子裡對演算法實現模模糊糊，無法正確寫出可行的演算法。現在看來，一方面是國內博客的實現有點脫離演算法導論里的原始代碼，另一方面也是因為還不知道循環不變數，直到因為研究生演算法課開始拜讀演算法導論，才了解到裡面的快排實現，以及演算法背後的循環不變數，頓時有點豁然開朗的感受，所以說要學習演算法分析與設計，只讀演算法導論一本書就夠了。

快排基於分治思想，所以從步驟上也無非是分為三步。以對數組A[p...r]進行排序為例，三步分治過程為：

  1. 分解

    數組A[p…r]被劃分為兩個(可能為空)子數組A[p…q-1]和A[q+1…r]，使得A[p…q-1]中的每一個元素都小於等於A[q]，而A[q]也小於等於A[q+1…r]中的每一個元素，其中，計算下標q是劃分過程最為重要的部分。
  2. 解決

    通過遞歸調用快速排序，對子數組A[p…q-1]和A[q+1…r]進行排序。
  3. 合併

    因為子數組都是原址排序的，所以不需要合併操作:數組A[p…r]已經有序。

由此可見，快速排序演算法最為關鍵的就在於劃分操作，找出作為劃分點的下標q，使得q左邊的元素都小於等於A[q]，而A[q]也小於等於q右邊的元素，我們將A[q]稱為主元(pivot element)，所以劃分演算法的第一步便是確定主元。

一般來說，我們總是選擇x=A[r]作為主元，並圍繞它來劃分A[p...r]。隨著程序的執行，數組被劃分為4個(可能為空的)區域。在第一輪迭代之前，以及每一次迭代後，這四個區域中的每一個區域都滿足一定的性質：

對任意數組下標k，有：

  1. 若p<= k <= i，則A[k] <= x
  2. 若i+1 <= k <= j-1，則A[k] > x
  3. 若k == r，則A[k] == x
  4. 若j <= k < r，對應位置的值與主元之間不存在特定的大小關係

這四個區域滿足的性質，就是快速排序的循環不變數。根據該循環不變數，我們可以容易寫出如下的劃分程序，以下為Python代碼實現。至於其中的原因，我想大家看到代碼很容易理解吧，比如當A[j] <= x時，此時A[j]可以補充到小於等於x的那部分，而相應的此時A[i+1]要麼是大於x的，直接與A[j]交換，此後j進行了加1，自然能保證A[j-1]>x的；要麼i+1==j，此時，等於交換A[j]本身，此後j加1，仍然滿足A[j-1]>x。以下為Python實現：

def partition(A, p, r): i = p - 1 x = A[r] for j in range(p, r): # j:[p, r-1] if A[j] <= x: i += 1 A[i], A[j] = A[j], A[i] # swap A[i] with A[j] i += 1 A[i], A[r] = A[r], A[i] return i

我們以在一個樣例數組上的劃分過程來直觀觀察該循環不變數。

  1. i=p-1, j=p, x=A[r]

i p,j r 0 1 2 3 4 5 6 7 | 2 | 8 | 7 | 1 | 3 | 5 | 6 | 4 |i = -1, j = 0, x = 4A[j] = 2 < 4i = i + 1 = -1 + 1 = 0swap A[i] with A[j] <===> swap A[0] with A[0]

初始狀態下，i=p-1和j=p，因為在p和i之間，i+1和j-1之間都不存在值，所以循環不變數的前兩個條件顯然都滿足。接下來的運行過程，大家可以自己動手在紙上畫一畫，有助於自己理解劃分過程

2. i=0, j=1

p,i j r 0 1 2 3 4 5 6 7 | 2 | 8 | 7 | 1 | 3 | 5 | 6 | 4 | <= x| i = 0, j = 1, x = 4 A[j] = 8 > 4

3. i=0, j=2

p,i j r 0 1 2 3 4 5 6 7 | 2 | 8 | 7 | 1 | 3 | 5 | 6 | 4 | <= x| >x|i = 0, j = 2, x = 4A[j] = 7 > 4

4. i=0, j=3

p,i j r 0 1 2 3 4 5 6 7 | 2 | 8 | 7 | 1 | 3 | 5 | 6 | 4 | <= x| >x |i = 0, j = 3, x = 4A[j] = 1 < 4i = i + 1 = 0 + 1 = 1swap A[i] with A[j] <===> swap A[1] with A[3]

5. i=1, j=4

p i j r 0 1 2 3 4 5 6 7 | 2 | 3 | 7 | 8 | 3 | 5 | 6 | 4 | <= x | > x |i = 1, j = 4, x = 4A[j] = 3 < 4i = i + 1 = 1 + 1 = 2swap A[i] with A[j] <===> swap A[2] with A[4]

6. i=2, j=5

p i j r 0 1 2 3 4 5 6 7 | 2 | 3 | 3 | 8 | 7 | 5 | 6 | 4 | <= x | > x |i = 2, j = 5, x = 4A[j] = 5 > 4

7. i=2, j=6

p i j r 0 1 2 3 4 5 6 7 | 2 | 3 | 3 | 8 | 7 | 5 | 6 | 4 | <= x | > x |i = 2, j = 6, x = 4A[j] = 6 > 4

8. i=2, j=7

p i r,j 0 1 2 3 4 5 6 7 | 2 | 3 | 3 | 8 | 7 | 5 | 6 | 4 | <= x | > x | =x|循環結束

從上述過程可以看出，在每一輪迭代的開始，該循環不變數始終是滿足的。

最後，swap A[i+1] with A[r]

p i q r,j 0 1 2 3 4 5 6 7 | 2 | 3 | 3 | 4 | 7 | 5 | 6 | 8 | <= x | =x| > x結束一次劃分

2. 變體實現

實際上也可以不選x=A[r]作為主元。

2.1 x=A[p]作為主元

可以選擇x=A[p]作為主元，相應的循環不變數要進行適當調整：

  1. 若p+1 <= k <= i，則A[k] <= x
  2. 若i+1 <= k <= j-1，則A[k] > x
  3. 若x == p，則A[k] == x
  4. 若j <= k <=r，對應位置的值與主元之間不存在特定的大小關係

仍以上面的樣例數組為例進行一次劃分操作，當劃分的迭代結束時，有：

p i r j 0 1 2 3 4 5 6 7 | 2 | 1 | 7 | 8 | 3 | 5 | 6 | 4 | <= x | > x

此時，不再是進行swap A[i+1] with A[r]，由於主元x=A[p]位於數組的最左端，主元位置應該換進的是小於等於x的元素，所以便是進行swap A[i] with A[p]操作，這樣交換後：

p i r j 0 1 2 3 4 5 6 7 | 1 | 2 | 7 | 8 | 3 | 5 | 6 | 4 | <= x| =x| > x

下標i就是要找的切分點。

2.2 選擇數組中的任意某個元素x=A[u]作為主元

這裡我們假設u != p同時u != r，除此之外對u的取值沒有限制。

基於此，我們的循環不變數可以調整為：

  1. 若p <= k <= i同時k != u，則A[k] <= x
  2. 若i+1 <= k <= j-1同時k != u，則A[k] > x
  3. 若k == u，則A[k] == x
  4. 若j <= k <= r同時k != u，對應位置的值與主元之間不存在特定的大小關係

只是這樣的話，當劃分操作的迭代過程經過位於p+1和r-1之間的主元時，需要進行特殊的加1操作跳過主元，並在迭代完成後依據主元與最終i所處的位置大小關係來決定如何進行交換操作，這樣就加大了演算法本身的複雜性，所以一般不採取這樣的方法。

但是從以上的分析可以，對於主元x的選取是任意的，只是相應的循環不變數有所不同，以及演算法本身的複雜性可能不同。為了避免主元出現在數組的中部，造成迭代過程額外的要跳過主元的複雜性，一般選擇尾元素x=A[r]或頭元素x=A[p]作為主元。

3. 三路劃分演算法

隨著我們對快排的熟悉，我們會發現目前的演算法對於有大量重複元素或者元素完全相同的數組時，會退化為一個O(n^2)的演算法。究其原因，是因為快速排序的運行時間依賴於劃分是否平衡，而平衡與否又依賴於用於劃分的元素。如果劃分平衡，那麼快速排序演算法性能與歸併排序一樣了，是O(nlgn)的複雜度；如果劃分不平衡，那麼快速排序的性能就接近於插入排序了，是O(n^2)的複雜度。

那數組元素完全一樣的極端情況，此時的劃分過程會將全部元素歸到小於等於主元x的區域，不存在大於x的區域。因此每次解決步驟遞歸調用快排演算法時，一邊數組規模只是比上一次減1，另一邊數組規模為0，所以就退化為一個每次減1的遞歸調用，而劃分過程需要遍歷整個子數組，即T(n)=T(n?1)+O(n)T(n)=T(n?1)+O(n)，容易得到T(n)=O(n^2)。

為此我們可以考慮將劃分進一步細化：劃分操作將數組元素有原來的兩類增加為三類：小於主元的，等於主元的，以及大於主元的，劃分完成後只對小於主元和大於主元的兩部分進行遞歸。

這就是三路劃分的思想，我們選擇x=A[r]作為主元，則此時的循環不變數為：

  1. 若p <= k <= i，則A[k] < x
  2. 若i+1 <= k <= e，則A[k] == x
  3. 若e+1 <= k <= j-1，則A[k] > x
  4. 若k == r，則A[k] == x
  5. 若j <= k < r，對應位置的值與主元之間不存在特定的大小關係

基於該循環不變數，我們的演算法改寫為如下，仍為Python實現：

def partition3(A, p, r): i = p - 1 x = A[r] for j in range(p, r): # j:[p, r-1] if A[j] < x: i += 1 A[i], A[j] = A[j], A[i] 1. p <= k <= i, A[k] < x 2. i+1 <= k <= r-1, A[k] >= x 3. k == r, A[k] == x 繼續處理A[i+1...r]之間大於等於x的元素 e = i for j in range(i+1, r): # j:[i+1, r-1] if A[j] == x: e += 1 A[e], A[j] = A[j], A[e] e += 1 A[e], A[r] = A[r], A[e] return i, e+1 # A[p...i] < x, A[e+1...r] > x

如果理解了上面的演算法，相信你也很容易理解該演算法，無非就是迭代過程先將元素分為小於主元和大於等於主元的兩部分，再對大於等於主元的部分進行細化，分為等於主元的和大於主元的兩部分，這樣就完成了三路劃分的任務。

光說不練不行，我們來刷一道LeetCode的題目Sort List來檢驗下效果。

題目要求：

要求對一單鏈表進行排序，時間複雜度限制在O(nlgn)，只能使用常量的地址空間。

參照三路劃分思想我們可以解決這個問題，同時注意到是單鏈表，一開始我們無法拿到尾元素tail.val作為主元，所以我們選擇首元素head.val作為主元。以下為我的代碼實現，同樣為Python：

# Definition for singly-linked list.# class ListNode(object):# def __init__(self, x):# self.val = x# self.next = Noneclass Solution(object): def sortList(self, head): """ :type head: ListNode :rtype: ListNode """ # 選擇None作為鏈表的結尾哨兵 self.quickSort(head, None) # 返回排序後的頭節點head return head def quickSort(self, head, tail): # List is not None and List has not only one element if head != tail and head.next != tail: pLt_next, pGt = self.partition3(head, tail) self.quickSort(head, pLt_next) self.quickSort(pGt, tail) def partition3(self, head, tail): pi = head x = head.val pj = head.next while pj != tail: if pj.val < x: pi = pi.next #print(pi, pj: %d %d % (pi.val, pj.val)) pi.val, pj.val = pj.val, pi.val pj = pj.next head.next -> ... -> pi, node.val < x pi.next -> ... -> pj, node.val > x pe = pi pj = pi.next while pj != tail: if pj.val == x: pe = pe.next pe.val, pj.val = pj.val, pe.val pj = pj.next head.val == x head.next -> ... -> pi, node.val < x pi.next -> ... -> pe, nonde.val == x pe.next -> ... -> tail.prev, node.val > x swap head.val with pi.val #print(head, pi: %d %d % (head.val, pi.val)) head.val, pi.val = pi.val, head.val head -> ... -> pi.prev, node.val < x pi -> ... -> pe, node.val == x pe.next -> ... -> tail.prev, node.val > x return pi, pe.next

調試了一些引用錯誤後，順利AC了!

4. 參考文章

  1. 【演算法雜談 1】 從一道面試題再看三路快排partition_慕課手記
  2. 演算法導論 原書第三版 第7章 快速排序
  3. Github CLRS/Chapter_07_Quicksort/exercises_7.1.md#7.1-2

推薦閱讀：

※前端排序之插入排序與希爾排序

TAG:排序演算法 | 快速排序 |