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