快速排序

思想：

分而治之，或者说递归，即大问题拆解成类似的小问题，把所有的小问题解决，就解决了大问题；

应用在快排（默认从小到大排序）上，就是取一基准点，遍历数组，将比基准点大的放在基准点右边，比基准点小的放在基准点左边；

然后再以同样的思路，在基准点左边序列中，重新取一基准点，重复上述流程，直到只需要比较一个元素和基准点的大小，即为有序

步骤：

1. 取基准点，一般取区间的第一个元素，然后分区，左区（比基准点小）+基准点+右区（比基准点大）；

2. 分区步骤：选取基准点和前后指针后，遍历区间，先从右往左，找到第一个比基准点小的元素， 左指针=右指针的值；然后从左往右，找到第一个比基准点大的元素，右指针=左指针的值，重复直到两指针相遇，相遇点=基准点的值；

3. 分区后的左区和右区重复第一步，递归的结束标志为左右区间相等；

代码：

#include <iostream>
#include <vector>
using namespace std;int partition(vector<int>& arr, int low, int high) {int pivot = arr[low];while (low < high) {while (low < high && arr[high] >= pivot) {high--;}arr[low] = arr[high];while (low < high && arr[low] <= pivot) {low++;}arr[high] = arr[low];}arr[low] = pivot;return low;
}void quickSort(vector<int>& arr, int low, int high) {if (low < high) {int pos = partition(arr, low, high);quickSort(arr, low, pos-1);quickSort(arr, pos+1, high);}
}int main() {vector<int> arr = {5,3,2,1,6,8,9};quickSort(arr, 0, arr.size()-1);for (const int & a : arr) {cout << a << endl;}return 0;
}