【c++】《算法导论》中的快速排序，通俗易懂

class Solution {
public:
    void quickSort(vector<int>& arr, int left, int right) {
        if(left >= right) // 递归中断条件
            return;
        int mid_value = arr[right]; //选取最后一位作为主元值
        int last_pos = left - 1; //介于left和last_pos之间的数小于等于主元值，记为小区间，last_pos是小区间的末位，此时还没有数在小区间内所以要减1
        for(int cur = left; cur <= right - 1; cur++) { //对除最后一个主元外的前面的所有数依次判定其放不放入小区间
            if(arr[cur] <= mid_value) { //当前位置上的值小于等于主元值时
                last_pos++; //为小区间开辟下一个位置（该位置可能就是当前位置）
                swap(arr[last_pos], arr[cur]); //将当前位置上的数和新开辟的小区间末位上的数交换
            }
        }
        swap(arr[++last_pos], arr[right]); //继续开辟位置将主元放入，此时主元为小区间末位，并且后面的数都大于主元值（如果有的话）
        quickSort(arr, left, last_pos - 1); //主元左边的数组进行递归
        quickSort(arr, last_pos + 1, right); //主元右边的数组进行递归
    }

    vector<int> MySort(vector<int>& arr) {
        if(arr.size() <= 1) //过滤简单情况
            return arr;
        quickSort(arr, 0, arr.size() - 1);
        return arr;
    }
};