1 算法描述
快速排序的思想是先选取一个锚节点，将数组中的全部节点与锚节点比较，小于锚节点的值在左侧，大于锚节点的值在右侧，直至将数组分为3部分：
- 左部分：小于锚节点的数组
- 中间：锚节点
- 右部分：大于锚节点的数组；
最后在左部分数组和右部分数组分别迭代，直至结束，此时得到升序数组。
2 算法模版
快速排序的模板分为两部分：
- 1 实现分区逻辑
- 2 控制分区的次数
实现分区逻辑：使用快慢指针将数组分为3个区段，小于 – 慢指针 – 大于 – 快指针 – 未知 – 锚节点。慢指针标记一个大于锚点的值，快指针用于查找小于锚点的值，交换用于逻辑处理。
- 1 使用最右边的值作为锚节点
- 2 初始化快慢指针为0
- 3 如果快指针节点的值小于锚节点，则快指针节点的值与慢指针节点的值交换，同时快慢指针的索引都+1
- 4 如果快指针的值大于等于锚节点，则快指针节点的索引+1，慢指针不变
- 5 通过while循环后，最后交换快慢指针的值，此时快指针指向的是锚节点。
int partition(vector &array, int left, int right) {
int pivot = array[right];
int slow = left, fast = left;
while (fast < right) {
if (array[fast] < pivot) {
swap(array[slow], array[fast]);
slow++;
}
fast++;
}
swap(array[slow], array[right]);
return slow;
}
控制分区的次数：此处可以参考二叉树的前序遍历，实际上分区控制和二叉树遍历是一致的。
- 1 处理分区逻辑
- 2 处理左分区逻辑
- 3 处理右分区逻辑
void quickSort(vector &array, int left, int right) {
if (left >= right)
return;
int middle = partition(array, left, right);
quickSort(array, left, middle - 1);
quickSort(array, middle + 1, right);
}