本文介紹了快速排序java.lang.StackOverflow錯誤的處理方法，對大家解決問題具有一定的參考價值，需要的朋友們下面隨著小編來一起學習吧！
問題描述
我嘗試計算在數組的中軸、第一軸、隨機軸已排序三種情況下快速排序算法的執行時間。
中間樞軸和隨機樞軸適用于任何大小，但如果大小大于25000，則第一個樞軸案例會產生堆棧溢出。
代碼如下：
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);
}
調用代碼如下：
double startTime1 = System.currentTimeMillis();
q_sort(0,size -1);
double stopTime1 = System.currentTimeMillis();
double elapsedTime1 = stopTime1 - startTime1;
System.out.println(elapsedTime1);
推薦答案
您沒有說明數組是如何生成的，但我懷疑它已經排序。
問題如下：如果對已排序的數組進行快速排序，第一個透視會導致以下遞歸：0..24999、1..24999、2..24999、3..24999、4..24999，這會占用大量堆棧空間并導致堆棧溢出。這是因為數組是0..24999，軸心是0，那么第二個分區將變成1..24999。
您應該刪除其中一個尾部調用。要消除哪個尾部調用取決于哪個分區較小。您希望遞歸處理的數據盡可能少。其中一個遞歸被簡單地替換為循環。這個尾遞歸消除已經在Quicksort and tail recursive optimization
中解釋過了
無論如何，我建議使用現有的快速排序算法，而不是自己編寫代碼，除非這是一個家庭作業問題。
這篇關于快速排序java.lang.StackOverflow錯誤的文章就介紹到這了，希望我們推薦的答案對大家有所幫助，
