划分
在这一过程中，通过一次数组扫描并设置两个指针 i和 j，形成所谓的“双指针遍历”，同时确保在扫描过程中满足以下条件：
[lo, i] 之间的元素都 <=pivot。
[i+1, j-1] 之间的元素都 >pivot。
[j, hi-1] 之间的元素未被扫描。
[lo, i] 之间的元素都 <=pivot。
[i+1, j-1] 之间的元素都 >pivot。
[j, hi-1] 之间的元素未被扫描。
划分扫描条件
我们来详细描述一下“双指针遍历”过程中的各个阶段：
1. 扫描初始化：
在扫描开始前，我们设置 i=lo-1和 j=lo以保持上述三个条件成立。
在初始状态下 [j, hi-1] 之间是所有未扫描的元素，[lo, i] (<=pivot) 和 [i+1, j-1] (>pivot) 的区间都不存在。
划分扫描初始化
2. 扫描过程：
当 A[j] > pivot时，j的值加 1。保证 [i+1, j-1] 之间的元素满足 >piovt。
动图 划分扫描过程 1
当 A[j] <= pivot时，i加 1，交换 A[i]和 A[j]的值之后，j再加 1。
这样同时保证了 [lo, i] 之间的元素满足 <=pivot，并且 [i+1, j-1] 之间的元素满足 >piovt。
动图 划分扫描过程 2
3. 扫描结束：
扫描完成时 j = hi，此时我们需要将支点 A[hi]置于正确位置。通过交换 A[hi]与 A[i+1]，支点就位，返回其索引。
动图 划分扫描结束
将上述的扫描过程转化为代码是一个有趣的挑战，你可以先思考一下如何实现。这里提供一个我编写的函数，以供参考：
defpartition(A, lo, hi):
pivot = A[hi]
i = lo - 1
forj inrange(lo, hi):
ifA[j] <= pivot :
i = i + 1
A[i], A[j] = A[j], A[i]
A[i + 1], A[hi] = A[hi], A[i + 1]
returni + 1
下面的视频更好地展示了双指针遍历扫描代码的执行过程：
视频 划分扫描执行过程
注意：你可以在我的 github 仓库中查看源代码
https://github.com/dingtingli/algorithm/blob/main/Code/quicksort01.py
递归：实现快速排序
我们来完成最后一步，通过递归不断地对子数组进行划分，直到每个子数组只有一个元素，此时整个数组就被排序完成。
defquicksort(A, lo, hi):
iflo < hi:
pivot_index = partition(A, lo, hi)
quicksort(A, lo, pivot_index - 1)
quicksort(A, pivot_index + 1, hi)
详细递归执行过程的静态示意图如下：
递归执行示意图
注意：你可以在我的 github 仓库中查看源代码
https://github.com/dingtingli/algorithm/blob/main/Code/quicksort01.py
双指针遍历
在划分过程中，我们采用了双指针技术，这是一种常见的算法策略。该技巧有以下常见步骤和策略：
确定指针的移动策略：确定如何移动两个指针以达到目的。
计算和更新结构：使用两个指针计算结果，并根据需要更新结果。
处理边界和特殊情况：考虑两个指针到达数组边界时的情况。
确定指针的移动策略：确定如何移动两个指针以达到目的。
计算和更新结构：使用两个指针计算结果，并根据需要更新结果。
处理边界和特殊情况：考虑两个指针到达数组边界时的情况。
动图 划分扫描过程
双指针技术不仅用于快速排序，还广泛应用于其他算法和问题，例如：在有序数组中查找特定和的两个数；计算数组的最大/最小子数组和；检测链表中是否存在环。
我们可以思考一下：是否还有其它双指针移动策略来实现快速排序中的划分过程？
另一种双向的双指针遍历策略
在上面的内容中，我们详细介绍了快速排序算法，并通过双指针遍历技术成功实现了算法的核心部分——划分（partition）。
这种算法不仅简单易懂，其代码量也相对较少。
但如果我们考虑到一种特殊情况：数组完全由相同的元素组成，根据先前的算法进行划分，性能就会非常糟糕。
此时，每次划分都会将长度为 n的数组分为长度为 n-1和 0的两个子数组。这导致递归深度达到了 n层，而每一层都需要 O(n)的时间复杂度来去除一个元素，因此总的运行时间达到了 O(n^2)。
动图 重复元素划分扫描过程
为了解决这个问题，我们对双指针的遍历方向进行了调整，采用了双向划分策略。
双向划分（partition）过程
首先，我们选择数组的第一个元素作为支点。在划分过程中，两个指针 i和 j分别初始化在数组的两端。
i从左侧开始向右扫描，直到找到一个大于等于支点的元素为止；而 j从右侧开始向左扫描，直至遇到小于等于支点的元素。在这个过程中，我们需要确保满足以下三个条件：
[lo, i-1] 之间的元素都 <=pivot。
[i, j] 之间的元素未被扫描。
[j+1, hi] 之间的元素都 >=pivot。
[lo, i-1] 之间的元素都 <=pivot。
[i, j] 之间的元素未被扫描。
[j+1, hi] 之间的元素都 >=pivot。
划分扫描条件
同样，我们也来详细描述一下这种“双指针遍历”过程中的各个阶段：
1. 扫描初始化：
扫描开始之前，设置 i=lo和 j=hi+1，确保上述条件得以满足。
划分扫描初始化
2. 扫描过程：
从数组左端开始，i向右扫描，直到遇到大于或等于支点的元素。
从数组右端开始，j向左扫描，直到遇到小于或等于支点的元素。
交换这两个元素，然后继续上述的扫描过程。
从数组左端开始，i向右扫描，直到遇到大于或等于支点的元素。
从数组右端开始，j向左扫描，直到遇到小于或等于支点的元素。
交换这两个元素，然后继续上述的扫描过程。
动图 划分扫描过程
3. 扫描结束：
当 i和 j两指针相遇时，扫描结束。此时，为了将支点 A[lo] 放置在其正确的位置，我们需要交换 A[lo] 与 A[j]。完成这一操作后，返回支点的索引值。
动图 划分扫描结束
将上述的扫描过程转化为代码是一个有趣的挑战，你可以先思考一下如何实现。这里提供一个我编写的函数，以供参考：
defpartition(arr, low, high):
pivot = arr[low]
i = low
j = high + 1
whileTrue:
i += 1
whilei <= high andarr[i] < pivot:
i += 1
j -= 1
whilearr[j] > pivot:
j -= 1
ifi > j:
break
arr[i], arr[j] = arr[j], arr[i]
arr[low], arr[j] = arr[j], arr[low]
returnj
值得注意的是，在 j向左扫描时，我们并未设置 j>=low的条件，因为支点正是 arr[low]，它不可能小于自己。
注意：你可以在我的 github 仓库中查看源代码
https://github.com/dingtingli/algorithm/blob/main/Code/quicksort02.py
重复元素数组
现在，我们再次考虑之前所提到的那种特殊情况：数组完全由相同的元素组成。
使用新的划分策略，当遇到相同元素时，扫描会停止，并交换 i和 j指针的值。这样的操作虽然增加了元素交换的次数，但是得到的子数组更加均衡，从而充分利用了分治策略，使得算法的运行时间仍为 O(nlogn)。
动图 重复元素划分扫描过程快速排序的优化
我们已经深入探讨了快速排序算法及其两种主要的划分策略。
动图 划分扫描过程 1
注意：你可以在我的 github 仓库中查看源代码
https://github.com/dingtingli/algorithm/blob/main/Code/quicksort01.py
动图 划分扫描过程 2
注意：你可以在我的 github 仓库中查看源代码
https://github.com/dingtingli/algorithm/blob/main/Code/quicksort02.py
这两种策略都使用了固定元素作为支点（pivot）。对于随机输入的数据，这样的方法通常都能取得良好的效果。
但是，对于特定的输入模式，例如完全升序的数组，选择第一个元素作为支点会导致划分后的子数组极其不平衡，从而影响排序效率。
优化策略1：选择更优的支点
为了确保划分后的子数组尽可能平衡，我们需要优化支点的选择策略。
计算数组的中位数可能代价昂贵。因此，一种简单而有效的方法是选择数组中的三个元素——首、尾和中点，并将其中的中值作为支点。
这样，我们能够大幅提高支点的选择质量。当然，为了进一步增强算法的鲁棒性，我们可以考虑从更多元素中选择支点。
defmedia_three(arr, lo, mid, hi):
a, b, c = arr[lo], arr[mid], arr[hi]
if(a <= b <= c) or(c <= b <= a):
returnmid
elif(b <= a <= c) or(c <= a <= b):
returnlo
else:
returnhi
注意：你可以在我的 github 仓库中查看源代码
https://github.com/dingtingli/algorithm/blob/main/Code/quicksort03.py
优化策略2：混合使用插入排序
对于较小的数组，插入排序往往比快速排序更为高效。因此，结合快速排序和插入排序，采用混合排序策略，可以进一步提高排序效率。
具体而言，当待排序的数组大小达到某一阈值时，我们切换到插入排序。
至于何时切换，即数组的大小阈值是多少，这与具体系统有关。
《算法》中提到，5-15 之间的值在大多数情况下都表现良好。《编程珠玑》中，建议选用 30-70 之间的值，其中 50 被认为是一个较为理想的选择。
当然，具体的阈值最好根据实际应用场景进行调整。
在以下的代码示例中，我们使用变量 M 作为这个阈值。
defquicksort(A, lo, hi):
M = 5
ifhi <= lo + M:
insertionsort(A, lo, hi)
return
pivot_index = partition(A, lo, hi)
quicksort(A, lo, pivot_index - 1)
quicksort(A, pivot_index + 1, hi)
注意：你可以在我的 github 仓库中查看源代码
https://github.com/dingtingli/algorithm/blob/main/Code/quicksort04.py
总结
快速排序之所以名副其实地“快速”，归功于它独特的算法设计。这种排序方法综合了分治策略和双指针遍历技术，使其在各种情况下都能高效地工作。
通过详细探讨快速排序的各个方面，包括其基本原理、划分策略、双指针遍历，以及优化技巧，我们可以更深刻地理解这一算法的精妙之处。
这些方法的结合不仅提升了算法的效率，还保证了其在各种场景下的适应性和稳定性。因此，无论是在理论上还是在实际应用中，都值得我们深入学习和应用。返回搜狐，查看更多