導致StackOverflowError的通用QuickSort

這是我正在處理的Java書中的練習題。基本上，目標是使用compareTo以遞增的順序對泛型類型的數組進行排序。導致StackOverflowError的通用QuickSort

我想使用QuickSort來做到這一點。這裏是我的代碼：

public static <T extends Comparable<? super T>> 
void sort (T[] arr) 
{ 
    // If arr is null, empty, 
    // or only has 1 element, 
    // it is already sorted 

    if (arr == null || arr.length == 0 
      || arr.length == 1) 
     return; 

    // Call overloaded sort method 

    sort(arr, 0, arr.length - 1); 
} 

// HELPER METHOD FOR SORT METHOD 

public static <T extends Comparable<? super T>> 
void sort(T[] arr, int left, int right) 
{ 

    // To be used while sorting 

    int i = left; 
    int j = right; 

    // Check if left and 
    // right indices are out 
    // of order. If they are, 
    // nothing can be done 

    if (right <= left) 
     return; 

    // Middle element used 
    // as pivot 

    T pivot = arr[(left + (right - left))/2]; 

    // temp will be used 
    // to swap elements later 

    T temp; 

    // QuickSort algorithm 

    while (i <= j) 
    { 
     // Look for values on 
     // the left greater than 
     // the pivot and values 
     // on the right smaller 
     // than the pivot 

     // When you find both, swap them 

     while (arr[i].compareTo(pivot) < 0) 
     { 
      i++; 
     } 

     while (arr[j].compareTo(pivot) > 0) 
     { 
      j--; 
     } 

     // Check that i hasn't 
     // passed j already 

     if (i <= j) 
     { 

      // Swap the items 

      temp = arr[i]; 
      arr[i] = arr[j]; 
      arr[j] = temp; 

      // Move both indices 
      // to their next position 

      i++; 
      j--; 
     } 
    } 

    // Recursive calls to the 
    // sort method 

    if (left < j) 
     sort(arr, left, j); 
    if (i < right) 
     sort(arr, i, right); 
}

麻煩的是，當我測試這個使用下面的數組：

String[] wordArray = {"Droplet", "Blueberry", "Elephant", 
      "Fate", "Apple", "Coconut", "Darjeeling"};

我會在以下行的StackOverflowError：

while (arr[i].compareTo(pivot) < 0)

然後一個一堆重複在這條線：

sort(arr, i, right);

上面的行重複錯誤告訴我，它可能與無限遞歸發生有關，但我不知道爲什麼會這樣。

我也不知道它爲什麼會在while循環線上拋出錯誤......它看起來像我用來比較arr [i]與pivot的邏輯是好的嗎？

來源

2017-04-15 enharmonics

不要重新發明輪子 - 使用[Collections框架]（http://docs.oracle.com/javase/7/docs/technotes/guides/collections/overview.html）並在'Collections.sort'方法中構建： –

線選擇中間元件，用於樞軸應該是：

T pivot = arr[left + (right - left)/2];

當前代碼被有效地使用T pivot = arr[right/2]，其中索引right/2可以小於左，導致不存在的樞軸值在從左到右的範圍內。

考慮使用小於左側範圍內的所有元素值的樞軸值的情況。這可能會導致第一個循環前進i過去right甚至超過陣列末尾，這可能會導致堆棧溢出或分段錯誤。

來源

2017-04-15 19:37:25 rcgldr

導致StackOverflowError的通用Qu​​ickSort

回答

相關問題

導致StackOverflowError的通用QuickSort