的中位數3，用迭代器快速排序

我試圖通過取出要排序的矢量的第一個，最後一個和中心元素的中值來選擇快速排序的樞軸。我已經看到很多以int爲範圍的實現，但是我試圖用迭代器來實現（不管怎麼說，它不應該是這樣）。然而，我的代碼劑量完全符合我的要求。它適用於T是int的情況，但對於其他類的超時。有任何想法嗎？下面是代碼：的中位數3，用迭代器快速排序

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

來源

2013-03-25 Sid

首先，你應該使用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-25 03:27:44 Yuushi

我已經遞減'end'在它傳遞到這個函數之前，所以我不認爲這是問題。我嘗試將int的類型更改爲size_type，並嘗試了difference_type，但它的工作量很大。 – Sid 2013-03-25 16:12:32

的中位數3，用迭代器快速排序

回答

相關問題