1

我正在尝试通过获取要排序的向量的第一个、最后一个和中心元素的中值来选择快速排序的枢轴。我已经看到了很多以 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
4

1 回答 1

0

首先，您应该使用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)
于 2013-03-25T03:27:44.033 回答