合并排序算法不工作

Question

我正在尝试实现一个不能正常工作的mergesort算法。合并排序的工作方式如下：

i、 将未排序的列表划分为n个子列表，每个子列表包含1个元素（1个元素的列表被视为已排序）。

ii.重复合并子列表以产生新排序的子列表，直到只剩下1个子列表。这将是已排序的列表。下面提供了实现。

最初，递归调用此方法，直到只有一个元素。

public void mergeSort(int low, int high) {

    if (low >= high) {
        return;
    }

    int middle = (low + high) / 2;

    // recursion for the merge
    mergeSort(low, middle);
    mergeSort(middle + 1, high);

    merge(low, middle, high);
}

这是提供的合并方法。

private void merge(int low, int middle, int high) {

    int i = low, j = middle;
    int index = low;

    for (int k = 0; k <= high; k++) {
        tempArray[k] = nums[k];
    }

    /*
      Copy the smallest values from either the left
      or the right side back to the original array
     */
    while ((i <= middle) && (j <= high)) {
        if (tempArray[i] <= tempArray[j]) {
            nums[index++] = tempArray[i++];
        } else {
            nums[index++] = tempArray[j++];
        }
    }

    // fill the left side of the array
    while (i < middle) {
        nums[index++] = tempArray[i++];
    }

    // fill the right side of the array
    while (j < high) {
        nums[index++] = tempArray[j++];
    }
  }

这里的问题是什么？

输入是int[]arr={12, 3, 4, 56, -7, 1}；输出是12 12 12 12 56 56

Answer 1

我修改了合并函数，现在它开始工作了。特别是，需要在中间项j=中间1之后初始化j

 private void merge(int low, int middle, int high) {

    int i = low, j = middle+1;
    int index = low;

    for (int k = 0; k <= high; k++) {
        tempArray[k] = nums[k];
    }

    /*
      Copy the smallest values from either the left
      or the right side back to the original array
     */
    while ((i <= middle) && (j <= high)) {
        if (tempArray[i] <= tempArray[j]) {
            nums[index++] = tempArray[i++];
        } else {
            nums[index++] = tempArray[j++];
        }
    }

    // fill the left side of the array
    while (i <= middle) {
        nums[index++] = tempArray[i++];
    }

    // fill the right side of the array
    while (j <= high) {
        nums[index++] = tempArray[j++];
    }
}