十一，算法-快速排序
在前面的部分已经讲过冒泡、选择、插入排序三种排序算法，本章节讲述快速排序，快速排序属于递归算法，同时很多语言的内置排序算法使用的就是快速排序。
定义
快速排序算法结合了分区和递归，步骤如下：
- 对数组执行分区，分区后，基准值处于数组中的正确位置；
- 对分区后的每个子数组继续执行1、2两个步骤，即不断分区；
- 当某个子数组没有或者只有一个元素，则这就是递归的基础情形，不做任何操作。
分区
快速排序依赖一个概念-分区。还是以数组为例，选取数组中的某个值作为基准，以该基准为分界线，将小于基准的数值移动到基准左侧位置，将大于基准的数值移动到基准右侧位置，步骤如下：
- 选择数组最右侧数值为基准；
- 创建两个指针，一个指向数组第一个（最左侧）数值，此处暂且称为左侧指针，另一个指针指向数组最右侧数值（此处排除基准值所在的位置），此处暂且称为右侧指针；
- 左侧指针不断右移，直到遇到大于或等于基准的数值才停止；
- 右侧指针不断左移，直到遇到小于等于基准的数值或者数组的第一个元素才停止；
- 右侧指针停止后出现两种情况，如果左侧指针和右侧指针相遇或者交错，即左侧指针指向元素的数组索引等于或大于右侧指针指向的元素的数组索引，则继续执行步骤6；否则交换左侧指针和右侧指针指向的数值，然后跳转到步骤3继续执行；
- 交换基准和左侧指针指向的数值；
完成上述步骤后，可以保证基准值已经处于数组中的正确位置，但基准值左侧是数值和右侧的数值可能并不是按顺序排列的。代码如下：
int partition(std::vector<int>& arr, int left, int right) {int pivotIndex{right};int pivot{arr[pivotIndex]};while (true) {while (arr[left] < pivot) {++left;}while (arr[right] > pivot) {++right;}if (left > right) {break;}else {std::swap(arr[left], arr[right]);++left;}}std::swap(arr[left], arr[right]);return left;}递归
接下来就是对分区后的子数组进行递归，最后的快速排序实现如下：
void quickSort(std::vector<int>& arr, int left, int right) {if (left >= right) return;int pivotIndex = partition(arr, left, right);quickSort(arr, left, pivotIndex - 1);quickSort(arr, pivotIndex + 1, right);}时间复杂度
快速排序包含两类主要操作：比较和交换。以一次分区为例，数组中所有数值都需要和基准进行比较，为N；但不是每次比较都需要交换数值，最多需要N/2次交换。这是一次交换的时间步骤数，再乘以分区次数，即为快速排序的时间复杂度，但进行多少次分区是无法确定的，因为数组的原始排序不可知，假设数组是平均情况（有顺序有逆序，差不多各一半），则统计下来快速排序的时间负责大概为O(Nlog(N))。对比之前的插入排序，平均情况下快速排序还是比插入排序的快很多。
快速选择
日常会遇到类似的算法题，即从数组中选出第十小或者第五大的数。一种解决方案是排序整个数组，再读取对应索引的数值，这种方法在平均情况下最快为O(Nlog(N))。另一种解决方案是部分使用快速排序的方法，可以称之为快速选择。快速选择即是将要找的数值索引与基准值索引做比较，这样每次都只需要对基准一侧的子数组进行递归，另一侧数组不用做额外处理，这种情况下快速选择的时间复杂度接近线性时间复杂度，即O(N)，代码如下：ku
int quickSelect(int queryValueIndex, std::vector<int>& arr, int left, int right) {if (left >= right) return;int pivotIndex = partition(arr, left, right);if(queryValueIndex < pivotIndex ){quickSelect(arr, left, pivotIndex - 1);}else if(queryValueIndex > pivotIndex){quickSelect(arr, pivotIndex + 1, right);}else{return arr[pivotIndex ];}}快速排序和快速选择都是递归算法，虽然实现过程没有那么直观，但效率确实排序算法中最好的。至此，关于递归的部分就基本结束。一部分数据结构中使用了递归操作，如二叉查找树的前、中、后需查找等，这部分将在后续的文章中继续介绍。