快排原理
def sort(L, R, ar):
if L >= R:
return
lf, rg = L, R
# 指定L处的数字为基准x
while lf < rg:
while rg > lf and ar[rg] >= ar[L]: rg -= 1 # 仅定位大于x的数
while lf < rg and ar[lf] <= ar[L]: lf += 1 # 仅定位小于x的数
-------------------------------------------------------------------------
关键点：上面两个while的顺序不能变，先 rg-- 再 lf++，不然会错误的交换数字
假设 rg-- 直到与 lf 重合，此时 lf 处的数字必定因为上次交换而小于x
假设 lf++ 直到与 rg 重合，此时 rg 处的数字必定因为while的终止条件而小于x
因此，不论是 lf 移动导致重合还是 rg 移动导致重合，最终 lf 指向的数字必定小于x
这确保了下面这个交换式(ar[L], ar[lf] = ar[lf], ar[L])的正确性
假设 lf 先入 while，必定碰到一个大于x的数而停下 或是 遇到因为上次交换而指向大于x
的数的 rg，无论哪种情况都可能导致将一个比x大的数与L处的基准交换
-------------------------------------------------------------------------
ar[lf], ar[rg] = ar[rg], ar[lf]
ar[L], ar[lf] = ar[lf], ar[L]
sort(L, lf-1, ar)
sort(lf+1, R, ar)
return
快排交换数列部分的两种写法
快排的其他实现
