在排序的算法中，1945 年由
冯·诺依曼 发明的归并排序（Merge Sort），是一种典型利用分治策略高效解决问题的算法。 看图聊算法：冯·诺依曼的第一个计算机程序
然而，归并排序的缺陷在于其需要额外存储空间。这引发了一个问题：能不能有一种算法 ，既不依赖额外空间，又能利用分治思想进行原地排序？ 快速排序正是这样一种算法。不同于归并排序，快速排序将重心放在“分”上，让“治”自然发生。
快速排序的核心原理 快速排序分为两个核心过程组成：
划分（Partition）： 选择数组中的一个元素为支点（pivot），通过一次遍历，将小于等于支点的元素移到左侧，大于支点的元素移动到右侧。
递归（recursion）： 对左右两侧的子数组，重复执行上述操作，直到整个数组完全有序。
选择合适的支点（pivot） 我们首先来选择支点（pivot），支点的选择对快速排序的效率影响显著。
理想情况下，支点选择数组中位数，这样能确保划分后的子数组尽量平衡，从而最大限度地发挥分治的效果。
但在实际操作中，每次都去找中位数从性能上看，似乎划不来。因此，对于随机排列的数组而言，直接选择最后一个元素作为支点，不失为一种好方法。
划分（Partition）过程 选择好支点后，我们可以对数组进行划分操作。这也是快速排序算法中最重要的部分。
划分 在这一过程中，通过一次数组扫描并设置两个指针 i 和 j ，形成所谓的“双指针遍历”，同时确保在扫描过程中满足以下条件：
[i+1, j-1] 之间的元素都 >pivot 。 划分扫描条件 我们来详细描述一下“双指针遍历”过程中的各个阶段：
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] ，支点就位，返回其索引。
动图 划分扫描结束 将上述的扫描过程转化为代码是一个有趣的挑战，你可以先思考一下如何实现。这里提供一个我编写的函数，以供参考：
def partition (A, lo, hi) : pivot = A[hi] i = lo - 1 for j in range(lo, hi): if A[j] <= pivot : i = i + 1 A[i], A[j] = A[j], A[i] A[i + 1 ], A[hi] = A[hi], A[i + 1 ] return i + 1 下面的视频更好地展示了双指针遍历扫描代码的执行过程：
视频 划分扫描执行过程 注意：你可以在我的 github 仓库中查看源代码 https://github.com/dingtingli/algorithm/blob/main/Code/quicksort01.py
递归：实现快速排序 我们来完成最后一步，通过递归不断地对子数组进行划分，直到每个子数组只有一个元素，此时整个数组就被排序完成。
def quicksort (A, lo, hi) : if lo < 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 。 [j+1, hi] 之间的元素都 >=pivot 。 划分扫描条件 同样，我们也来详细描述一下这种“双指针遍历”过程中的各个阶段：
1. 扫描初始化 ：
扫描开始之前，设置
i=lo 和 j=hi+1 ，确保上述条件得以满足。
划分扫描初始化 2. 扫描过程 ：
从数组左端开始， i 向右扫描，直到遇到大于或等于支点的元素。 从数组右端开始， j 向左扫描，直到遇到小于或等于支点的元素。 动图 划分扫描过程 3. 扫描结束 ：
当 i 和 j 两指针相遇时，扫描结束。此时，为了将支点 A[lo] 放置在其正确的位置，我们需要交换 A[lo] 与 A[j]。完成这一操作后，返回支点的索引值。
动图 划分扫描结束 将上述的扫描过程转化为代码是一个有趣的挑战，你可以先思考一下如何实现。这里提供一个我编写的函数，以供参考：
def partition (arr, low, high) : pivot = arr[low] i = low j = high + 1 while True : i += 1 while i <= high and arr[i] < pivot: i += 1 j -= 1 while arr[j] > pivot: j -= 1 if i > j: break arr[i], arr[j] = arr[j], arr[i] arr[low], arr[j] = arr[j], arr[low] return j 值得注意的是，在 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：选择更优的支点 为了确保划分后的子数组尽可能平衡，我们需要优化支点的选择策略。
计算数组的中位数可能代价昂贵。因此，一种简单而有效的方法是选择数组中的三个元素——首、尾和中点，并将其中的中值作为支点。
这样，我们能够大幅提高支点的选择质量。当然，为了进一步增强算法的鲁棒性，我们可以考虑从更多元素中选择支点。
def media_three (arr, lo, mid, hi) : a, b, c = arr[lo], arr[mid], arr[hi] if (a <= b <= c) or (c <= b <= a): return mid elif (b <= a <= c) or (c <= a <= b): return lo else : return hi 注意：你可以在我的 github 仓库中查看源代码
https://github.com/dingtingli/algorithm/blob/main/Code/quicksort03.py
优化策略2：混合使用插入排序 对于较小的数组，插入排序往往比快速排序更为高效。因此，结合快速排序和插入排序，采用混合排序策略，可以进一步提高排序效率。
具体而言，当待排序的数组大小达到某一阈值时，我们切换到插入排序。
至于何时切换，即数组的大小阈值是多少，这与具体系统有关。
《算法》中提到，5-15 之间的值在大多数情况下都表现良好。《编程珠玑》中，建议选用 30-70 之间的值，其中 50 被认为是一个较为理想的选择。
当然，具体的阈值最好根据实际应用场景进行调整。
在以下的代码示例中，我们使用变量 M 作为这个阈值。
def quicksort (A, lo, hi) : M = 5 if hi <= 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
总结 快速排序之所以名副其实地“快速”，归功于它独特的算法设计。这种排序方法综合了分治策略和双指针遍历技术，使其在各种情况下都能高效地工作。
通过详细探讨快速排序的各个方面，包括其基本原理、划分策略、双指针遍历，以及优化技巧，我们可以更深刻地理解这一算法的精妙之处。
这些方法的结合不仅提升了算法的效率，还保证了其在各种场景下的适应性和稳定性。因此，无论是在理论上还是在实际应用中，都值得我们深入学习和应用。
