QuickSort永不停止

我試圖實現快速排序算法，但是當我運行它時，永遠不會停止，結果是StackOverflowException。QuickSort永不停止

（我知道，使用兩個燃料電池堆到rearange陣列，像我一樣，它是不是最有效的方式，但在這個時候，這是不是那麼重要。）

private static void quickSort(int[] a, int start, int end) { 
     if (start >= end) { 
      return; 
     } 

     int pivot = a[start]; 
     Stack<Integer> left = new Stack<Integer>(); 
     Stack<Integer> right = new Stack<Integer>(); 

     for (int i = start + 1; i <= end; i++) { 
      if (a[i] < pivot) { 
       left.push(a[i]); 
      } else { 
       right.push(a[i]); 
      } 
     } 

     int arrayIndex = 0; 
     int middle = 0; 

     while (left.size() > 0) { 
      a[arrayIndex++] = left.pop(); 
     } 

     middle = arrayIndex; 
     a[arrayIndex++] = pivot; 

     while (right.size() > 0) { 
      a[arrayIndex++] = right.pop(); 
     } 

     quickSort(a, start, middle - 1); 
     quickSort(a, middle + 1, end); 
    }

來源

2015-01-09 VCODE

int arrayIndex = 0;

必須替換爲

int arrayIndex = start;

來源

2015-01-09 17:22:21 laune

它仍然會以相同的值溢出。（使用Stack在遞歸過程中會導致顛倒順序，當數組中沒有相等的值時，可以避免溢出） – NiematojakTomasz

謝謝！你是對的，改變'arrayIndex = start'就可以修復它。但是pivot不會被推送到'right'堆棧，因爲pivot必須是'a [start]'，但迭代從'start + 1'開始。 – VCODE

我沒有看到第一回合的首發+1。刪除了第二次更正！ – laune

QuickSort永不停止

回答

相關問題