java - 合并算法

Question

下面是 Java 中合并排序的合并实现:

void merge(int[] numbers, int low, int mid, int high) {
    int helper[] = new int[numbers.length];
    for (int i = low; i <= high; i++) {
         helper[i] = numbers[i];
    }

    int lowone = low;
    int lowtwo = mid + 1;
    int count = low;

    while (lowone <= mid || lowtwo <= high) {
        if (lowone <= mid && lowtwo <= high) {
            if (helper[lowone] <= helper[lowtwo]) {
                numbers[count] = helper[lowone];
                lowone++;
            } else {
                numbers[count] = helper[lowtwo];
                lowtwo++;
            }
        }
        else if (lowone <= mid) {
              numbers[count] = helper[lowone];
              lowone++;
            }
        else {
              numbers[count] = helper[lowtwo];
              lowtwo++;

        }
       count++;
    }
}
//msort algorithm in case it's relevant
void msort(int[] arr, int low, int high) {
    if (low < high) {
        int mid = (low + high)/2;

        msort(arr, low, mid);
        msort(arr, mid + 1, high);

        merge(arr, low, mid, high);
    }
}

在我第一次尝试合并时，我试图让数组的后半部分包含中点索引，而不是在前半部分中包含它。这是相关代码(注意上面只有 4 处更改):

    int lowtwo = mid;

    while (lowone < mid || lowtwo <= high) {
        if (lowone < mid && lowtwo <= high) {
            if (helper[lowone] <= helper[lowtwo]) {
                numbers[count] = helper[lowone];
                lowone++;
            } else {
                numbers[count] = helper[lowtwo];
                lowtwo++;
            }
        }
        else if (lowone < mid) {
              numbers[count] = helper[lowone];
              lowone++;
        }
        else {
              numbers[count] = helper[lowtwo];
              lowtwo++;   
        }

与 msort(上面)一起使用的修改版本无法正确对列表进行排序。也许这是显而易见的，但我似乎无法弄清楚为什么它不起作用。

Answer 1

问题的出现是因为你改变了合并中 mid 的含义。最简单的查看方法是一个例子。假设我们有一个带有索引的数组:

[0 1 2 3 4]

调用 msort，您将传入 0 表示低值，4 表示高值。这意味着 mid 被计算为 2。所以你现在已经将数组划分为这样(不是在内存中，只是逻辑上):

[0 1 2] [3 4]

现在，当调用 merge 时，它​​会传入 2 作为 mid，这是数组 1 中的最后一个索引。但是，在修改后的代码中，您将 mid 视为数组 2 的起始索引。这使得两个数组看起来像像:

[0 1] [2 3 4]

这与一切对待它的方式不同。一个例子是，如果你有两个数组(排序后)看起来像(数字现在是值，而不是索引):

[8 12 14] [7 11]

但是，根据您对 mid 的解释，数组是:

[8 12] [14 7 11]

不再排序。因此你的合并功能将无法工作。