本文介紹了快速排序java.lang.StackOverflow錯(cuò)誤的處理方法，對(duì)大家解決問題具有一定的參考價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)吧！
問題描述
我嘗試計(jì)算在數(shù)組的中軸、第一軸、隨機(jī)軸已排序三種情況下快速排序算法的執(zhí)行時(shí)間。
中間樞軸和隨機(jī)樞軸適用于任何大小，但如果大小大于25000，則第一個(gè)樞軸案例會(huì)產(chǎn)生堆棧溢出。
代碼如下：
static void q_sort( int left, int right)
{
int pivot;
int l_hold, r_hold;
l_hold = left;
r_hold = right;
pivot = array[left];
while (left < right)
{
while ((array[right] >= pivot) && (left < right))
right--;
if (left != right)
{
array[left] = array[right];
left++;
}
while ((array[left] <= pivot) && (left < right))
left++;
if (left != right)
{
array[right] = array[left];
right--;
}
}
array[left] = pivot;
pivot = left;
left = l_hold;
right = r_hold;
if (left < pivot)
q_sort(left,(int) pivot-1);
if (right > pivot)
q_sort( (int)pivot+1, right);
}
調(diào)用代碼如下：
double startTime1 = System.currentTimeMillis();
q_sort(0,size -1);
double stopTime1 = System.currentTimeMillis();
double elapsedTime1 = stopTime1 - startTime1;
System.out.println(elapsedTime1);
推薦答案
您沒有說明數(shù)組是如何生成的，但我懷疑它已經(jīng)排序。
問題如下：如果對(duì)已排序的數(shù)組進(jìn)行快速排序，第一個(gè)透視會(huì)導(dǎo)致以下遞歸：0..24999、1..24999、2..24999、3..24999、4..24999，這會(huì)占用大量堆棧空間并導(dǎo)致堆棧溢出。這是因?yàn)閿?shù)組是0..24999，軸心是0，那么第二個(gè)分區(qū)將變成1..24999。
您應(yīng)該刪除其中一個(gè)尾部調(diào)用。要消除哪個(gè)尾部調(diào)用取決于哪個(gè)分區(qū)較小。您希望遞歸處理的數(shù)據(jù)盡可能少。其中一個(gè)遞歸被簡單地替換為循環(huán)。這個(gè)尾遞歸消除已經(jīng)在Quicksort and tail recursive optimization
中解釋過了
無論如何，我建議使用現(xiàn)有的快速排序算法，而不是自己編寫代碼，除非這是一個(gè)家庭作業(yè)問題。
這篇關(guān)于快速排序java.lang.StackOverflow錯(cuò)誤的文章就介紹到這了，希望我們推薦的答案對(duì)大家有所幫助，
