從錯過的函數調用堆棧溢出

Question

對不起，如果這張貼在其他地方（我找不到任何東西，因爲我的問題是比較具體的），但我理解（或至少在理論上）錯誤是什麼;我在如何修復它時遇到了麻煩。代碼應該顯示合併排序的工作方式;代碼運行，但它從來沒有命中函數調用「合併」（下面的代碼，我知道在進口中調用全部是不好的做法，但它不是一個主要項目，所以我不在乎;也許它是隻是預覽，但它被寫入import java.util。;和import java.security。;）。

import java.util.*; 
import java.security.*; 

public class Merge { 
    public static void mergeSort(int[] data) { 
     sortArray(data, 0, data.length - 1); 
    } 

    private static void sortArray(int[] data, int low, int high) { 
     if ((high - low) >= 1) { 
      int m1 = low + high; 
      int m2 = m1 + 1; 

      System.out.printf("Split: %s\n", subarrayString(data, low, high)); 
      System.out.printf("   %s\n", subarrayString(data, low, m1)); 
      System.out.printf("   %s\n\n", subarrayString(data, m2, high)); 

      sortArray(data, low, m1); 
      sortArray(data, m2, high); 

      merge(data, low, m1, m2, high); 
     } 
    } 

    public static void merge(int[] data, int l, int m1, int m2, int r) { 
     int lIndex = l, rIndex = r, cIndex = l, combined[] = new int[data.length]; 

     System.out.printf("Merge: %s\n", subarrayString(data, l, m1)); 
     System.out.printf("    %s\n", subarrayString(data, m1, r)); 

     while (lIndex <= data[rIndex]) { 
      if (data[lIndex] <= data[rIndex]) 
       combined[cIndex++] = data[lIndex++]; 
      else 
       combined[cIndex++] = data[rIndex++]; 
     } 

     if (lIndex == m2) 
      while (rIndex <= r) combined[cIndex++] = data[rIndex++]; 
     else 
      while (lIndex <= m1) combined[cIndex++] = data[rIndex++]; 
    } 

    private static String subarrayString(int[] data, int low, int high) { 
     StringBuilder temp = new StringBuilder(); 

     for (int i = 0; i < low; i++) 
      temp.append("  "); 

     for (int i = 0; i < high; i++) 
      temp.append(" " + data[i]); 

     return temp.toString(); 
    } 

    public static void main2() { 
     SecureRandom gen = new SecureRandom(); 

     int[] data = new int[10]; 

     for (int i = 0; i < data.length; i++) data[i] = 10 + gen.nextInt(50); 

     System.out.printf("\nUnsorted Array:\n%s\n\n", Arrays.toString(data)); 
     mergeSort(data); 
     System.out.printf("\nSorted Array:\n%s\n\n", Arrays.toString(data)); 
    } 
} 

讓我知道你是否需要驅動文件。重申，問題是它永遠不會到達合併函數調用並導致堆棧溢出錯誤。

Answer 1

堆棧溢出的常見原因是遞歸調用錯誤。通常，這是在您的遞歸函數沒有正確的終止條件時引起的。在你的代碼中，第一次遞歸調用總是調用相同的參數0和（長度 - 1）並且不終止，並且它將陷入無限循環。修復你的代碼並更新m1的值，以便它終止。

考慮數組長度爲6：

low = 0 and high = 5 
m1 = 5 
sortArray(data, 0, 5);