Quick Sort
快排
算法思路
快排的算法思想是分治:
- 分:将整个序列分为左右两个子序列,左边的子序列小于等于x,右边的子序列大于x,这个x我们称为主元(pivot),用它来分割序列
- 治:子序列递归执行
- 合:左右两个子序列均已排序,中间的主元满足要求,因此得到的就是最终结果
算法正确性
因为主元所在的位置与最终已排序序列的位置是一致的,那么依次分割,将序列切短至长度为1,那么自然就得到了最终的排序序列
实现
1 | QUICKSORT(A,p,r) |
我们用PARTITION来获取主元:
1 | PARTITION(A,p,r) |
用循环不变式可以证明PARTITION的正确性:
- $p \le k \le i ,A[k] \le pivot$
- $i+1 \le k \le j-1 ,A[k]>pivot$
- $k=r,A[k]=pivot$
$Proof:$
- 初始:$i=p-1,j=p,[p,i]$和$[i+1,j-1]$没有元素存在
- 维持:只有当$A[j] \le x$时$i$才会前进,而$j$是无条件递增的,交换$A[i]$和$A[j]$,使得$A[i] \le x$,$A[j]$获得了原来的$A[i+1]>x$,下一次循环前我们还要自增一次,因此$k \le j-1$依然满足循环不变式
- 终止:当循环终止时,$j=r$,那么$p \le k \le i ,A[k]\le x ,i+1 \le k \le r-1, A[k]>x$
在终止之后,我们将$A[i+1]$和$A[r]$交换(不是和$A[i]$),就得到了主元在序列中的位置
快排的关键才做在于partition()
,而partition()
的关键在于循环不变式的理解,主要是指其中i
,j
的理解,它究竟是如何维护循环不变式的。
先说结论,
i
是分隔标志i
是小于等于主元的右边界,i+1
是大于主元的区域的左边界。
j
是大于主元的区域的右边界。而j
最终到达r
。
也就是说它形成了两个区域:
因此partition()
的逻辑就是维护循环不变式,只要保证循环不变式不被破坏,那么最后只要swap(A[i+1], A[r])
即可。
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Conzxy's blog!
评论