数据结构：快速排序算法详解（双指针法）
快速排序（双指针·递归）
算法思想
双指针排序是利用两个指针协助操作来完成排序的任务，它们通常同向移动或者相向移动。典型的运用场景如下：
- 快速排序：通过分区操作将数组分为小于/大于基准值的两部分进行递归。
- 归并排序：合并两个有序子数组时，通过双指针比较元素大小。
为了方便理解，总结两个指针的原理（cur 是前指针，prev 是后指针）：
- cur 找小，找到小之后，prev 再找大，然后二者交换对应的元素，cur 再向前移动。
- prev 找大，找到大之后，与 cur 所指的值进行交换。
实现步骤
在进行正式的学习之前，我们先来看一下它的动图，好好感悟一下，然后进行思路拆分讲解：
- 数据初始化。
- 指针功能拆分：
- cur：找小（对于基准值而言），因为我们需要与 prev 所指向的进行交换，小的交换到左边去。
- prev：找大（对于基准值而言），因为我们需要将其与 cur 所指的内容进行交换，大的要到右边去。
- 前后指针法，cur 要先动，cur 找到小之后，prev 再动，直到找到较大的元素（注意：prev 不能跑到 cur 的前面去）。
- 当 prev 与 cur 重合时，进行交换，交换之后 cur 再加加，进入新一轮的判断。
- 循环执行上述过程，直到 cur 出了数组界限，最后将 prev 所指的与 pivot 位置进行交换，更新 pivot，单趟结束。
- 接下来以基准值为界限，分为左右两组进行递归。
复杂度分析
- 最好时间复杂度、平均时间复杂度：每次分区操作的时间复杂度为 O(n)，递归树的深度为 log n，总操作次数为 O(n log n)。
- 最坏时间复杂度：每次分区之后，一个子数组为空，另一个子数组包含剩余的所有元素，时间复杂度为 O(n^2)。
- 空间复杂度：递归树的深度为 log n。
代码实现
单趟实现
按照上面的原理，先实现单趟：cur 找小，找到之后 prev 再找大【prev 不能超过 cur】，交换之后，cur++；prev 找大，找到之后交换。
while (cur <= right) { // 找小
if (arr[cur] < arr[pivot]) {
prev++;
// 交换
Exchange(&arr[prev], &arr[cur]);
cur++;
}
if (arr[cur] > arr[pivot]) {
cur++;
}
}
// 此时 right=size，交换 left 与 pivot 下标的元素
Exchange(&arr[pivot], &arr[prev]);
// 更改 pivot 的位置
pivot = prev;
递归实现
对于递归，强调一下思路，借助代码来分析：
int left = 0;
int right = size - 1;
void QuickSort(* arr, left, right) {
(left >= right) {
;
}
pivot = (arr, left, right);
(arr, left, pivot - );
(arr, pivot + , right);
}
