快速排序的深入分析-数据分析方法梅长林

五、快速排序的深入分析

咱们再具体分析下上述的优化版本， PARTITION(A, p, r):

1  x ← A[r]

2  i ← p - 1

3  for j ← p to r - 1

4      do if A[j] ≤ x

5          then i ← i + 1

6          exchange A[i] <-> A[j]

7  exchange A[i + 1] <-> A[r]

8  return i + 1

咱们以下数组进行排序，每一步的变化过程是：

i    p/j  2  8  7  1  3  5  6  4(主元)

i    j    2  1  7  8  3  5  6  4

i    j    2  1  3  8  7  5  6  4

i         2  1  3  4  7  5  6  8

由上述过程，可看出，j扫描了整个数组一遍，只要一旦遇到比4小的元素，i就++，然后，kj、ki交换。那么，为什么当j找到比4小的元素后，i要++呢? 你想，如果i始终停在原地不动，与kj每次交换的ki不就是同一个元素了么? 如此，还谈什么排序? 所以，j在前面开路，i跟在j后，j只要遇到比4小的元素，i就向前前进一步，然后把j找到的比4小的元素，赋给i，然后，j才再前进。

打个比喻就是，你可以这么认为，i所经过的每一步，都必须是比4小的元素，否则，i就不能继续前行。好比j是先行者，为i开路搭桥，把小的元素作为跳板放到i跟前，为其铺路前行啊!