Java MergeSort算法遞歸

Question

我有一個小問題。 我嘗試實現合併排序算法遞歸。

int sort_list[] = {5, 9, 7, 8, 3, 4, 5, 6, 1, 0}; 
int[] left = new int[sort_list.length]; 
int[] right = new int[sort_list.length]; 

public Mergesort() { 
    int[] lv_sorted_list = mergeSort(sort_list); 
    for (int i = 0; i < lv_sorted_list.length; i++) { 
     System.out.print(" " + lv_sorted_list[i] + ", "); 
    } 
} 

int[] mergeSort(int[] iv_sort_list) { 

    for (int i = 0; i < iv_sort_list.length; i++) { 
     System.out.print("Divide: " + iv_sort_list[i] + " "); 
    } 
    System.out.println(""); 

    if (iv_sort_list.length > 1) { 
     left = mergeSort(Arrays.copyOfRange(iv_sort_list, 0, iv_sort_list.length/2)); 
     right = mergeSort(Arrays.copyOfRange(iv_sort_list, iv_sort_list.length/2, iv_sort_list.length)); 
    } 
    int i = 0; 
    int j = 0; 
    int[] sorted_list = new int[left.length + right.length]; 
    while (i < left.length && j < right.length) { 
     if (left[i] > right[j]) { 
      int tmp = left[i]; 
      left[i] = right[j]; 
      right[j] = tmp; 
      System.arraycopy(left, 0, sorted_list, 0, left.length); 
      System.arraycopy(right, 0, sorted_list, left.length, right.length); 
      i++; 
      j++; 
     }else{ 
      break; 
     } 
    return sorted_list; 
} 

現在我的問題：

left = mergeSort(Arrays.copyOfRange(iv_sort_list, 0, iv_sort_list.length)); right = mergeSort(Arrays.copyOfRange(iv_sort_list, iv_sort_list.length, iv_sort_list.length));

如果我嘗試分配我的左/右陣列「歸併（......）」，那麼它將只分配了新的新數組長，其中包含在每個位置值0

非常感謝您的幫助:)

Answer 1

我認爲你缺少的基本情況iv_sort_list.length = 1或iv_sort_list.length = 2（取決於您的實現）在您的遞歸函數中。

你的left[]和right[]應該在每個遞歸調用中聲明嗎？由於您在那裏使用的屬性很多，如果您聲明爲具有固定長度的全局屬性，則會出錯。

而且您的合併代碼似乎有點亂，我已經修改了一下，現在它應該工作，請在這裏看到的例子：Merge Sort (Java) demo