我的快速排序實現有什麼問題？

關於我的幼稚快速排序算法只是一個快速（哈哈）問題：我的快速排序實現有什麼問題？

#include <iostream> 

template <class T> 
void quicksort2(T array[] , int start, int end){ 
    int i = start; 
    int j = end; 
    int temp; 
    int pivot = (end - start)/2; 

    // Partioning 
    while(i <= j){ 

    while(array[i] < array[pivot]){ 
     i++; 
    } 
    while(array[j] > array[pivot]){ 
     j--; 
    } 

    if(i <= j){ 
     temp = array[i]; 
     array[i] = array[j]; 
     array[j] = temp; 
     i++; 
     j--; 
    } 
    } 

    // Sorting partions 
    if(start <= j){ 
    quicksort2(array , start , j); 
    } 
    if(end >= i){ 
    quicksort2(array , i , end); 
    } 
}

當我運行一個測試陣列上的代碼，它似乎只有陣列（不到邊的左側）被排序並且不會跳轉到排序右側並創建一個無限循環。

運行代碼之前有點警告，有時會在我測試陣列上運行代碼時凍結我的機器。

無論如何，感謝您的幫助！此外，這不是用於作業（什麼類與排序算法需要你馬上學習快速排序？）

來源

2014-01-17 The Alex

快速排序是我在大學的高級算法課程中學到的第一個算法，就像永遠以前一樣。 –

你正在運行windows嗎？ –

你使用'temp'是有點危險的。 'temp'是'int'但是'array [i];'在'temp = array [i];'是'T'。我會建議使用['std :: swap']（http://en.cppreference.com/w/cpp/algorithm/swap），但看起來很愚蠢。我用手寫了10次，9次好，1次錯。討厭的錯誤。 'std :: swap（array [i]，array [j]）'應該這樣做，並且已經被模板化了。 – luk32

我會用問題回答你的問題。

如何處理在start == end時調用方法的情況？

每次運行都會將您的小節圍繞數據點進行分割，因此每次遞歸運行時，您都有上次的1/2的長度。所以，你首先排序前半部分，然後是第一個1/4，然後是第一個1/8。最終，您將調用start = end = 0的方法。這使得0 - 0/2是數據透視表，它是0.

通過您的代碼運行該案例，您會看到您不是處理您的方法嘗試對其自身排序一個條目的情況。它會卡在一個無限的遞歸循環，直到它崩潰與...

堆棧溢出。

來源

2014-01-17 15:51:42

另外，你的數據透視計算是錯誤的。如果你的開始和結束是2和4，那麼4 - 2 = 2/2 = 1。所以你的樞紐指數超出開始，結束的範圍。 –

此外內部循環不是交叉檢查（當'我'穿過'j'），所以你可以繼續前進。 – wmorrison365

@LouLouviere啊，樞紐計算是不是我的意思是它。我曾打算將它作爲（左+右）/ 2。感謝您的支持。在解決這個問題並實現代碼來處理你描述的情況之後，代碼現在可以正常工作。萬分感謝！ –

你可能想看看你使用'='。我相信你可以使用> =和< =與樞軸點進行比較，但在進行交換時不需要。

然後kicker是遞歸調用 - 你肯定不想使用=那裏，我認爲這是一個無限遞歸的原因，它最終會崩潰，因爲j永遠不會比起始少。所以基本上每一個都與一個=比較，刪除它，每一個沒有=的比較，都加一個。

來源

2014-01-17 16:03:48

我的快速排序實現有什麼問題？

回答

相關問題