＃1的錯誤而執行插入排序使用遞歸

Question

public static void insertionSortRecursion(String a[], int first, int last) { 
     if (first < last) { 
      //sort all but last 
      insertionSortRecursion(a, first, last - 1); 
      insertInOrder(a[last], a, first, last -1); 
     } 
    } 

    private static void insertInOrder(String element, String[] a, int first, int last) { 
//  System.out.println(last - 1); 
//  System.out.println(element); 
//  System.out.println(a[last]); 
     if (element.compareTo(a[last]) >= 0) { 
      a[last + 1] = element; 
     } else if(first < last) { 
      a[last + 1] = a[last]; 
      insertInOrder(element, a, first, last - 1); 
     } else { 
      a[last + 1] = a[last]; 
      a[last] = element; 
     } 
    } 

嗨， 我想那種使用遞歸這是對少數詞的做工精細，以實現插入，但我實現它，因爲文件的大小，我以後越來越計算器排序有大約10,000個單詞。請建議我應該怎麼做以消除錯誤。

These are the methods I am using for insertion sort using recursion and I am calling them in my constructor. 

Answer 1

Java默認情況下無法處理deep（10000）的遞歸深度。考慮下面的簡單例子，仍然會拋出StackOverflowError。

static void test(int i) 
{ 
    if (i == 0) return; 
    test(i-1); 
} 

public static void main(String[] args) 
{ 
    test(10000); 
} 

必須指定命令行參數來實現這一點（-Xss和可能-Xmx分配更多的存儲器）。

我使用-Xmx1000m -Xss10000000（儘管需要一段時間）成功運行了一個大小爲100000的數組。

我假設你有使用遞歸的原因，而不是簡單的double for循環。

Answer 2

假設您的算法是正確的，請保留此功能。不要試圖修復它。一般來說擺脫堆棧溢出（同時保持遞歸）有兩種解決方法：

• 使用tail call optimization
• 增加堆棧大小

但是，讓坐下來承擔這個代碼將除了編程練習之外別無他法。任何其他需要閱讀的人都會認爲：

1. 爲什麼他使用插入排序？
2. 爲什麼他重新執行插入排序？
3. 是否必須遞歸？我的主！！
4. 爲什麼他浪費時間去尋找一個tail-call插入算法？或者
5. 他是否僅僅爲了運行他的方法而增加了堆棧大小？
6. 好。現在我們有1000,000項目進行排序和程序不斷崩潰。

結論是，他們會立即清除您的代碼並使用Collections.sort()。 正如我所說，如果你正在做一個編程練習，那麼很好，你的遞歸插入排序工作，直到某一點。繼續。