先来分析一下基础快排的问题，再来实现双指针快排
分析基础快排
有两个哨兵
lt和i， 它们都向右移动
lt记录当前序列 小于基准值区间内的最后一位元素
i遍历整个[left, right]区间：
- 发现小于等于 基准值的元素，则与
lt位置的元素进行交换- 发现大于 基准值的元素，跳过不做任何操作
发现问题
在下面这个例子中存在大量重复元素，在进行一次切分操作后，切分点的位置是 11
此时，这个数组被分成的两部分是不平衡的，左边的元素远远多余右边
这就造成了 递归树倾斜 ， 在之前说到了，快排的效率快慢在于递归树的深度，所以，我们应尽量使 切分 趋于两边平衡。
在这个示例中出现递归树倾斜的原因是有大量重复元素，为了使递归树平衡，我们可以将这些重复元素在左右两部分都分配一点，而不是全分配到一边
解决思路
寻找：
这次切分内的遍历不从一边开始，从两端开始
ge从left + 1开始遍历，寻找大于等于基准值的数，找到后退出遍历le从right开始遍历，寻找小于等于基准值的数，找到后退出遍历
说明：
lt是less than的缩写，表示（严格）小于；gt是greater than的缩写，表示（严格）大于；le是less than or equal的缩写，表示小于等于（本代码没有用到）；ge是greater than or equal的缩写，表示大于等于（本代码没有用到）。
交换：
两个哨兵都退出遍历后，交换这两个元素的位置
退出：
当 ge 在 le 的右侧时，表示左右两边已分配完毕，退出循环，交换基准值与较小区间中最后一个元素的位置
def partition(arr, left, right):
pivot = arr[left]
ge = left + 1
le = right
while 1:
# 寻找
while ge <= right and arr[ge] < pivot:
ge += 1
# 退出循环，ge所在位置元素 大于或等于pivot
while le >= left + 1 and arr[le] > pivot:
le -= 1
# 退出循环，le所在位置元素 小于或等于pivot
# 退出
if ge > le:
break
# 交换
arr[ge], arr[le] = arr[le], arr[ge]
ge += 1
le -= 1
# 交换基准值与较小区间中最后一个元素的位置
arr[left], arr[le] = arr[left], arr[le]
return le
疑惑解答
1、这个切分为什么能将元素平衡的分配到两边？
观察下面演示图
通过这种方式的切分，使得重复元素被平均分配到两边
观察上图，也说明了 快速排序 是不稳定的排序，等值元素间前后位置在交换的过程中发生了改变
2、为什么返回的是 le
while le >= left + 1 and arr[le] > pivot:
le -= 1
在这个循环退出时，我们知道 le 所指的就是小于或等于 基准值的元素，所以在整个循环退出后，le最后所指的就是较小区间内最后一个元素的位置
双路快排的切分演示
完整代码
import random
def insert_sort(arr, left, right):
for i in range(left + 1, right + 1):
temp = arr[i]
p = i - 1
while p >= left and arr[p] > temp:
arr[p + 1] = arr[p]
p -= 1
arr[p + 1] = temp
def partition(arr, left, right):
pivot = arr[left]
ge = left + 1
le = right
while 1:
while ge <= right and arr[ge] < pivot:
ge += 1
# 这个循环退出，代表l当前所在位置的值大于等于 pivot
while le >= left + 1 and arr[le] > pivot:
le -= 1
# 这个循环退出，代表r当前所在位置的值小于等于 pivot
if ge > le:
break
arr[ge], arr[le] = arr[le], arr[ge]
ge += 1
le -= 1
# 基准值与小部分的最后一个元素值进行交换
arr[left], arr[le] = arr[le], arr[left]
return le
def quick_sort(arr, left, right):
if left >= right:
return
# 优化1：小规模用插入排序
if right - left <= 15:
insert_sort(arr, left, right)
return
# 优化2：每次随机选择基准值
random_index = random.randint(left, right)
arr[left], arr[random_index] = arr[random_index], arr[left]
p_index = partition(arr, left, right)
quick_sort(arr, left, p_index - 1)
quick_sort(arr, p_index + 1, right)
@cal_time
def quick_sort_test(arr):
# arr = [0, 2, 5, 1, -4]
# quick_sort(arr, 0, len(arr) - 1)
quick_sort(arr, 0, len(arr) - 1)
print(arr)
总结
双指针快排就是把等于切分元素的所有元素等概率地分到了数组的两侧，避免了递归树倾斜，递归树相对平衡；
参考文章：