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;
}