从快速排序看循环不变量
原文链接： 从快速排序看循环不变量 in wangzhike.github.io
1. 基本思路
大概三年前我第一次知道有个快速排序算法，当时才接触分治思想不久，加上直接是参考国内一些博客的文章，虽然写出了可以正确运行的快排程序，但始终觉得有点雾里看花，无法把握算法的基本思想，这也导致一段时间过后，我在徒手写快排程序，脑子里对算法实现模模糊糊，无法正确写出可行的算法。现在看来，一方面是国内博客的实现有点脱离 算法导论里的原始代码 ，另一方面也是因为还不知道 循环不变量 ，直到因为研究生算法课开始拜读算法导论，才了解到里面的快排实现，以及算法背后的循环不变量，顿时有点豁然开朗的感受，所以说 要学习算法分析与设计，只读算法导论一本书就够了 。
快排基于分治思想，所以从步骤上也无非是分为三步。以对数组 A[p...r] 进行排序为例，三步分治过程为：
-
分解
数组 A[p…r] 被划分为两个(可能为空)子数组 A[p…q-1] 和 A[q+1…r] ，使得 A[p…q-1] 中的每一个元素都小于等于 A[q] ，而 A[q] 也小于等于 A[q+1…r] 中的每一个元素，其中， 计算下标 q 是划分过程最为重要的部分 。 -
解决
通过递归调用快速排序，对子数组 A[p…q-1] 和 A[q+1…r] 进行排序。 -
合并
因为子数组都是原址排序的，所以不需要合并操作:数组 A[p…r] 已经有序。
由此可见，快速排序算法最为关键的就在于划分操作，找出作为划分点的下标 q ，使得 q 左边的元素都小于等于 A[q] ，而 A[q] 也小于等于 q 右边的元素，我们将 A[q] 称为 主元(pivot element) ，所以划分算法的第一步便是确定主元。
一般来说，我们总是选择 x=A[r] 作为主元，并围绕它来划分 A[p...r] 。随着程序的执行， 数组被划分为4个(可能为空的)区域 。在第一轮迭代之前，以及每一次迭代后，这四个区域中的每一个区域都满足一定的性质：
对任意数组下标 k ，有：
- 若 p<= k <= i ，则 A[k] <= x
- 若 i+1 <= k <= j-1 ，则 A[k] > x
- 若 k == r ，则 A[k] == x
- 若 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我们以在一个样例数组上的划分过程来直观观察该循环不变量。
- 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 = 4
A[j] = 2 < 4
i = i + 1 = -1 + 1 = 0
swap 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 |
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 = 4
A[j] = 7 > 44. 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 = 4
A[j] = 1 < 4
i = i + 1 = 0 + 1 = 1
swap 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 = 4
A[j] = 3 < 4
i = i + 1 = 1 + 1 = 2
swap 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 = 4
A[j] = 5 > 47. 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 = 4
A[j] = 6 > 48. 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] 作为主元，相应的循环不变量要进行适当调整：
- 若 p+1 <= k <= i ，则 A[k] <= x
- 若 i+1 <= k <= j-1 ，则 A[k] > x
- 若 x == p ，则 A[k] == x
- 若 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 的取值没有限制。
基于此，我们的循环不变量可以调整为：
- 若 p <= k <= i 同时 k != u ，则 A[k] <= x
- 若 i+1 <= k <= j-1 同时 k != u ，则 A[k] > x
- 若 k == u ，则 A[k] == x
- 若 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] 作为主元，则此时的循环不变量为：
- 若 p <= k <= i ，则 A[k] < x
- 若 i+1 <= k <= e ，则 A[k] == x
- 若 e+1 <= k <= j-1 ，则 A[k] > x
- 若 k == r ，则 A[k] == x
- 若 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 = None
class 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