提供堆棧溢出錯誤的簡單QuickSort算法？

我的朋友有一個小問題，我在我的知識結束。他寫了一個簡單的（他在學校）QuickSort算法它會產生一個StackOverflow錯誤。我知道這意味着它會在某個地方多次調用遞歸，但我無法獲得邏輯錯誤 - 請幫助我！提供堆棧溢出錯誤的簡單QuickSort算法？

下面是代碼（我要離開了一些代碼，這只是顯示它在2文本區域）：

int array [] = new int [10]; 
... 
public static void quicksort (int array[],int l,int r){ 
int i = l; 
int j = r; 
int mitte = array [(l+r)/2]; 

while (i<j) { 
    while (array[i]<mitte) { 
    i++; 
    } // end of if 
    while (mitte<array[i]) { 
    j--; 
    } // end of if 
    if (i<=j) { 
    int merke =array[i]; 
    array[i] = array [j]; 
    array [j] = merke ; 
    i++; 
    j--; 
    } // end of if 
    if (i<j) { 
    quicksort(array,l,j); 
    } // end of if 
    if (l<r) { 
    quicksort(array,l,r); 
    } // end of if 
} // end of while 
}

它被稱爲是這樣的：

quicksort(array,0,9);

但，如果我們稱之爲2號碼，它不會產生溢出。

如果需要更多的代碼，這裏是引擎收錄的全碼：http://pastebin.com/cwvbwXEu

來源

2014-01-27 Marenthyu

首先，這裏有一個無限循環：

while (mitte<array[i]) { 
    j--; 
    } // end of if

它需要array[j]

其次（並且導致無限遞歸），在第二次調用快速排序

if (l<r) { 
    quicksort(array,l,r); 
} // end of if

在遞歸中，你總是需要縮短自己調用的範圍，否則將會是無限的。我還沒有制定出你在做什麼，但我認爲你的意思是：

if (i<r) { 
    quicksort(array,i,r); 
} // end of if

來源

2014-01-27 18:38:26 mackworth

這似乎是我的朋友從一個簡單的抄板錯誤。謝啦。 – Marenthyu

還要注意，遞歸不應該在while循環中。快速排序是（1）將數組分成兩組，一組全部低於你的「數據透視」中間數字和一個以上，然後（2）用一次調用將每個組排序，每組快速排序。 – mackworth

這一呼籲：

if (l<r) { 
    quicksort(array,l,r); 
}

遞歸調用quicksort與獲得通過的是，而不是一個調用相同的參數較小的子問題來解決。因此它會無限地緩和。

來源

2014-01-27 18:30:28

if (l<r) 
quicksort(array,l,r);

Isnt l總是小於r？這將導致無限遞歸，這就是爲什麼如果兩個值都相同，您不會發生溢出。

來源

2014-01-27 18:31:33 user2535749

* doh *當然！對不起，我的啞巴XD - 感謝您的快速幫助！ – Marenthyu

提供堆棧溢出錯誤的簡單QuickSort算法？

回答

相關問題