Java合并排序递归算法

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

现在我的问题：

左=合并排序（rrays.copyOfRange（iv_sort_list，0，iv_sort_list.length））；右=合并排序（rrays.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（取决于您的实现）。

您的左[]和右[]应该在每个递归调用中声明？由于您经常使用那里的长度属性，如果您声明为具有固定长度的全局，则会出错。

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