0

这是用于合并排序的合并实现，在 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（上图）一起使用的修改版本无法正确排序列表。也许这很明显，但我似乎无法弄清楚为什么它不起作用。

4

2 回答 2

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]

不再排序。因此，您的合并功能将不起作用。

于 2012-12-30T05:16:05.663 回答
1

msort(...)这是因为在与第二个子数组 (in ) 中的中点合并之前，您已经使用第一个子数组 (in ) 中的中点对两个子列表进行了排序merge(...)。

举个最简单的例子

[2,1]

像这样分裂（因为 mid == ((0+1)/2) == 0 ）

[2] 和 [1]

哪个 msort 微不足道地排序

[2] 和 [1]

但是，通过将 mid 放在合并的第二个列表中，您实际上是在合并：

[] 和 [2,1]

这显然导致[2,1]，这是错误的！

中点放置在两个子阵列的拆分和合并中必须保持一致。

于 2012-12-30T05:34:36.150 回答