Java MergeSort Algorithm recursive

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));

如果我尝试分配我的左/右数组"mergeSort（...）"，那么它将只分配一个具有新长度的新数组，该数组在每个位置都包含值 0。

非常感谢您的帮助:)

Answer 1

我认为您在递归函数中缺少基本情况iv_sort_list.length = 1或iv_sort_list.length = 2（取决于您的实现）。

您的left[]和right[]应该在每个递归调用中声明吗？由于您经常使用属性length因此，如果您以固定长度声明为全局，则会出错。

另外，您的合并代码似乎有点混乱，我已经修改了一些，现在它应该可以工作了，请参阅此处的示例：合并排序（Java）演示