使用向量和迭代器C ++实现的通用Qu ickSort

Question

我尝试使用迭代器编写一个通用的快速排序，但是当我编译它时我得到了这个错误：

“在实例化'void QuickSortRec（std :: vector，Iter，Iter）[使用T = int; Iter = __gnu_cxx :: __ normal_iterator>]'：Iterators.cpp：49：53：从这里需要Iterators.cpp：133： 28：错误：'operator /'不匹配（操作数类型是'__gnu_cxx :: __ normal_iterator>'和'int'）Iter pivot（_begin +（_ end / 2））;“

这是我的代码：

template<typename T, typename Iter>
void QuickSortRec(std::vector<T> _vector, Iter _begin, Iter _end)
{
    Iter pivot(_begin + (_end / 2));
    Iter left(_begin);
    Iter right(_end);

    while (left <= right)
    {
        while (*left < *pivot)
        {
            ++left;
        }

        while (*right > *pivot)
        {
            --right;
        }

        if (*left >= *right)
        {
            Swap(left, right);
            ++left;
            --right;
        }
    }

    if (_begin < right)
    {
        QuickSortRec(_vector, _begin, right);
    }

    if (left < _end)
    {
        QuickSortRec(_vector, left, _end);
    }
}

template<typename Iter>
void Swap(Iter _a, Iter _b)
{
    Iter temp(_b);
    *_b = *_a;
    *_a = *temp;
}

Answer 1

Hoare分区类型快速排序的示例。通常Hoare将索引指定为-1和大小，但不允许等效于-1的迭代器，因此第一个实例在进入主循环之前使用等效的0和size-1。

template <typename I>
void QuickSort(I beg, I end)
{
    if (end - beg < 2)
        return;
    I lft(beg);
    I rgt(end-1);
    auto pvt = *(lft + (rgt-lft)/2);
    if(*lft < pvt)
        while (*++lft < pvt) ;
    if(*rgt > pvt)
        while (*--rgt > pvt) ;
    while (lft < rgt)
    {
        std::iter_swap(lft, rgt);
        while (*++lft < pvt) ;
        while (*--rgt > pvt) ;
    }
    rgt++;
    QuickSort(beg, rgt);
    QuickSort(rgt, end);
}