C++ 排序算法
快速排序
思想：
分而治之，或者说递归，即大问题拆解成类似的小问题，把所有的小问题解决，就解决了大问题；
应用在快排（默认从小到大排序）上，就是取一基准点，遍历数组，将比基准点大的放在基准点右边，比基准点小的放在基准点左边；
然后再以同样的思路，在基准点左边序列中，重新取一基准点，重复上述流程，直到只需要比较一个元素和基准点的大小，即为有序
步骤：
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;
}