c++ - 3 的中位数，使用迭代器进行快速排序

Question

我正在尝试通过取要排序的 vector 的第一个、最后一个和中心元素的中值来选择快速排序的基准。我已经看到很多关于 int 范围的实现，但我试图用迭代器来实现它。(无论如何它不应该有那么大的不同)。但是，我的代码完全按照我的意愿去做。它在 T 是一个 int 时有效，但对于其他一些类它会超时。有任何想法吗？这是代码:

template <class T>
int ParallelSort::partition(typename vector<T>::iterator &start, typename        vector<T>::iterator &end)
{
int Index = (end-start)/2;
T tmpSwap = start[Index];
//the three if statement get the three part median for the vector. 
if(start[Index] < *start)
{
    start[Index] = *start;
    *start = tmpSwap;
}
if(*end < *start)
{
    tmpSwap = *end;
    *end = *start;
    *start = tmpSwap;
}
if(*end < start[Index])
{
    tmpSwap = start[Index];
    start[Index] = *end;
    *end = tmpSwap;
}
T pivot = start[Index];
//rest of the code .....
//i'm sure that the rest of the code works correctly

Answer 1

首先，您应该使用 typename std::vector<T>::size_type , 不是 int .其次，使用 std::distance找到两个迭代器之间的差异，应该存储在 typename std::vector<T>::difference_type 中.最后，迭代器通常按值传递，而不是按引用传递。

您的问题可能是您要取消引用 end .这是未定义的行为 - 你可能想取消引用 --end .

此外，迭代器的全部意义在于您不会将自己限制在特定的容器中(无论如何在理论上)。这可能应该用签名写成:

template <typename SizeType, typename RandomAccessIterator>
SizeType ParallelSort::partition(RandomAccessIterator start, RandomAccessIterator end)