快速排序简便写法，一次遍历找到pivot

“快速排序”简便写法，一次遍历找到pivot

int Partition(vector<int>& arr, int l, int r)
{
    int i = l, pivot = arr[r];   //将数祖最后一位设为pivot
    for(int j = l; j < r; ++j)  //j记录比pivot小的值
    {                            //i记录比pivot大的值
        if(arr[j] < pivot)       
        {
            swap(arr[i++], arr[j]);  //将大的值和小的值进行交换
        }
    }
    swap(arr[i], arr[r]);     //最后将pivot的值与遍历结束位置的值且比它小的值进行交换
    return i;
}

void QuickSort(vector<int>& arr, int l, int r)
{
    if(l < r)
    {
        int pivot = Partition(arr, l, r);
        QuickSort(arr, pivot + 1, r);
        QuickSort(arr, l, pivot - 1);
    }
}
vector<int> MySort(vector<int>& arr) {
    int l = 0, r = arr.size() - 1;
    QuickSort(arr, l, r);
    return arr;
}