1 原理

伪代码：

1. 定义 arr[l ,r], j 指向 <p 的最后一个元素, i 待 patition 元素
2. 选择标定点 p(通常随机或第一个)，将数组 arr 分为以下两部分（等于号在哪侧对排序正确性无影响）
   • arr[l, j] < p
   • arr[j+1, r] >= p
3. 将标定点 p 交换到 j 的位置
4. 递归处理 arr[l, j-1] 和 arr[j+1, r]

2 单路 partition 优化

1. 通用优化：高级排序算法在递归到底层时都可以用插入排序进行优化，这是由于插入排序能够在察觉到有序数组时提前终止，并且对于几乎有序且数量较少的数组时间复杂度可达到O(n)；
2. 随机选择标定点 p 进行 partition：对于一般情况下 partition 过程如左图所示，但是对于一个有序或近乎有序的数组我们每次都是将整个除第一个元素以外的元素传入下一层递归，这会使得快速排序退化到O(n^2)

因此，我们使用随机选择标定点的方式，此时通过数学上的推导证明此时快速排序时间复杂度的期望值是O(nlogn)。此时，我们不能保证这个算法一定非常快，但是可以保证算法在99.99%也就是非常高的概率是非常快的