请你来手写一下快排的代码

void QuickSort(vector<int>& a,int left,int right){
    if(left < right){
        int pivot = Partition(vector<int>& a,int left,int right);
        
        QuickSort(a,left,pivot-1);
        QuickSort(a,pivot+1,right);
    }
}

int Partition(vector<int>& a,int left,int right){
    int pivotnum = a[left];
    while(left < right){
        while(left < right && a[right] >= pivotnum)    righ--;
        swap(a[left],a[right]);
        while(left < right && a[left] <= pivotnum)    left++;
        swap(a[left],a[right]);
    }
    return left;
}

template <class RAIter, class Cmp = std::less<>>
void quicksort(RAIter first, RAIter last, Cmp cmp = Cmp{}) {
    if(first == last) return;
    auto pivot = *std::next(first, std::distance(first, last) / 2);
    auto left = first, right = std::prev(last);
    for(; left <= right; ++left, --right) {
        while(cmp(*left, pivot)) ++left;
        while(cmp(pivot, *right)) --right;
        if(left > right) break;
        std::iter_swap(left, right);
    }
    quicksort(first, std::next(right), cmp);
    quicksort(left, last, cmp);
}

用标准库：

template <class ForwardIt, class Cmp = std::less<>>
void quicksort(ForwardIt first, ForwardIt last, Cmp cmp = Cmp{}) {
    if(first == last) return;
    auto pivot = *std::next(first, std::distance(first, last) / 2);
    auto middle1 = std::partition(first, last, 
                        [pivot](const auto &e){ return cmp(e, pivot); });
    auto middle2 = std::partition(middle1, last, 
                        [pivot](const auto &e){ return !cmp(pivot, e); });
    quicksort(first, middle1);
    quicksort(middle2, last);
 }

std::partition(first, last, pred)能够将[first, last)范围内的元素分成两组，pred得到true的元素排在false的元素前面，并且返回第二组元素的第一个。

C++11规定的std::partition只需要ForwardIterator，这种迭代器只需要向前操作，不知道怎么做到的。我自己实现的需要<=各种比较，因此是RandomAccessIterator

比较器用了std::less<>，需要C++14