合并算法

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

在我第一次尝试合并，我想有数组的后半部分包含中点指数，而不是具有它在上半场。这里是relavent代码（注意，是从上面只有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传给高。这意味着中期被计算为2。所以，你现在有分为左右（未在内存中，只是逻辑上）数组：

[0 1 2] [3 4] 

现在，当合并被称为它在2过去了中旬，这是最后一个在阵列然而指数，在你修改后的代码你把作为中期开始索引数组2.这使得两个数组看起来像：

[0 1] [2 3 4] 

这是不同的一切又如何对待它。这个地方倒下的一个例子是，如果你两个数组（排序后）看起来像（数字现在是值，而不是指数）：

[8 12 14] [7 11] 

然而，在你中旬解释，阵列是：

[8 12] [14 7 11] 

哪些不再排序。因此，你的合并功能将无法正常工作。

Answer 2

这是因为您已经在第一个子数组中的中点（msort(...)）中排序了第二个子数组中的中点（merge(...)）中的两个子列表。

以最简单的例子

[2,1]

被分裂像这样的（因为中间==（（0 + 1）/ 2）== 0）

[2]和[1]

其中msort平凡分类成

[2]和[1]

但N，通过合并将在中期的第二个列表，你实际上合并：

[]和[2,1]

这显然导致[2,1]，这是不对的！

中点位置在两个子阵列的分裂和合并中必须一致。