命名排序算法。它是QuickSort嗎？

1.當我填寫的範圍矢量[max-num, 0]（最壞的情況），我得到的方式比O(n^2)更好的結果。（我甚至不確定我是否寫過一個快速排序）。

2.當我混合範圍，例如：我填充未排序的矢量[0, max-num/2]然後[max-num/2, 0]，奇怪的是它運行崩潰到數字900,000，但後來崩潰。

template<class writeIter> 
void quicksort(writeIter begin, writeIter end) 
{ 
if (begin!= end) { 
    int diff = end-begin; 
    if (diff > 2) { 

     writeIter pivot = ((end-begin)/2) + begin; 
     writeIter itFirst = begin; 
     writeIter itSecnd = end-1; 
     auto pivotVal = *pivot; 

     swap(*pivot, *(end-1)); 
     while (itFirst < itSecnd) { 
      if (*itFirst > pivotVal) { 
       while (*itSecnd > pivotVal && itSecnd > itFirst) --itSecnd; 
       if (itSecnd > itFirst) 
        swap(*itFirst, *itSecnd); 
      } 
      ++itFirst; 
     } 
     swap(*itSecnd, *(end-1)); 

     quicksort(begin, itSecnd); 
     quicksort(itSecnd, end); 
    } 
    else if (diff == 2) 
     if (*begin > *(begin+1)) 
      swap(*begin, *(begin+1)); 
} 
}

來源

2016-03-30 scarface382

您有*三個*問題。第一個答案是'是'，模塊錯誤。 – EJP

你可能有堆棧溢出。該算法將每次選擇一個非常糟糕的支點（接近最大值），並將該範圍劃分爲極不平坦的部分。這對快速排序很不利。 –

是的，這是天真的快速排序。但是你選擇中間元素而不是最後一個元素作爲你的支點。

當填充一個矢量[MAX-NUM，0]，它實際上是不是最壞的情況可言。因爲每次選擇中間元素作爲關鍵點時，都會將矢量分成幾部分大小相同的兩部分，因此時間複雜度爲O（nlogn）。但是，當您填充未排序的矢量[0，max-num/2]，然後[max-num/2，0]時，對於您的算法來說，這是最糟糕的情況，因爲您將矢量分成兩部分，一部分極其嚴重長而且極短。所以時間複雜度是O（n^2）。

要在幾乎所有矢量獲得更好的性能，您可以：

選擇一個隨機元素作爲支點
挑選三個隨機元素和選擇的第二大一個
當向量的大小足夠小，例如小於10，應用插入排序
爲了處理所有元素彼此接近的情況，可以在遞歸地將子向量排序爲sk之前做一些額外的工作ip元素等於樞軸點

來源

2016-03-30 07:33:26

我改變了選擇樞軸到一個隨機的位置，並且它勝過std :: sort，如果我做了上面提到的混合範圍。感謝您提供有用的提示:)。 – scarface382

此外，標題是災難性的！這真的很晚，所以我甚至不確定當我問這個問題時是否清醒。 – scarface382

:)不客氣！ –

命名排序算法。它是QuickSort嗎？

回答

相關問題