java - 合并排序中的子数组大小

Question

我无法理解合并排序中子数组的大小。在以下代码中:

   public void mergeSort(List<Integer> list, int low, int high){

       if(low<high){
           int mid = (high+low)/2;
           mergeSort(list,low, mid);
           mergeSort(list,mid+1,high);
           merge(list, low, mid, high);

       }
   }

   private void merge(List<Integer> list ,int low, int mid, int high){

       int lSize = mid-low+1;
       int rSize = high-mid;
   //etc 
   }

对于子数组的大小，我必须在左边加 1，而右边的数组不加 1。我知道如果我们有一个大小为 10 的数组，索引将是 0..9 和 lSize将是 4-0+1，rSize 是 9-4。

我不太确定如何表达这个意思，但我无法思考在何处添加 +1，而无需在脑海中完成大小为 10 的整个示例数组。如果我暂时不接触合并排序，我会忘记在何处添加 +1。有没有更简单的方法来记住这个？谢谢。

Answer 1

溢出漏洞

首先，永远不要先加后除索引。如果数组非常大并且接近数组末尾，则 low 和 high 索引在溢出 Integer.MAX_VALUE 时总和可能为负数。然后，将其除以二将得出负值，而不是您期望的正值。

这是 a Google blog post about the issue . Java 中更正的方法是(注意是>>>，不是>>>):

int mid = (high + low) >>> 1;

推理

话虽如此，下面是解决问题的困难方法，然后是解决问题的简单方法。

问题是如何处理偶数或奇数 low 值和偶数或奇数 high 值，以便左侧和右侧的大小始终相当平衡。

让我们用可接受的 lSize 和 rSize 值制作一个适当平衡的表:

┏━━━━┯━━━━━━━┳━━━━━━━━━━━━┳━━━━━━━━━━━━┓
┃ low ╲ high ┃     4      ┃     5      ┃
┣━━━━━━┷━━━━━╋━━━━━━━━━━━━╇━━━━━━━━━━━━┫
┃     0      ┃ 2/3 or 3/2 │    3/3     ┃
┣━━━━━━━━━━━━╉────────────┼────────────┨
┃     1      ┃    2/2     │ 2/3 or 3/2 ┃
┗━━━━━━━━━━━━┻━━━━━━━━━━━━┷━━━━━━━━━━━━┛

相关的 mid 值为:

┏━━━━┯━━━━━━━┳━━━┳━━━┓
┃ low ╲ high ┃ 4 ┃ 5 ┃
┣━━━━━━┷━━━━━╋━━━╇━━━┫
┃     0      ┃ 2 │ 2 ┃
┣━━━━━━━━━━━━╉───┼───┨
┃     1      ┃ 2 │ 3 ┃
┗━━━━━━━━━━━━┻━━━┷━━━┛

因此，我们知道它会是类似mid - low 和high - mid 的东西，但我们可能需要对其进行调整。这些加起来等于您正在处理的总规模吗？

┏━━━━┯━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━┓
┃ low ╲ high ┃           4           ┃           5           ┃
┣━━━━━━┷━━━━━╋━━━━━━━━━━━━━━━━━━━━━━━╇━━━━━━━━━━━━━━━━━━━━━━━┫
┃     0      ┃ (2 - 0) + (4 - 2) = 4 │ (2 - 0) + (5 - 2) = 5 ┃
┣━━━━━━━━━━━━╉───────────────────────┼───────────────────────┨
┃     1      ┃ (2 - 1) + (4 - 2) = 3 │ (3 - 1) + (5 - 3) = 4 ┃
┗━━━━━━━━━━━━┻━━━━━━━━━━━━━━━━━━━━━━━┷━━━━━━━━━━━━━━━━━━━━━━━┛

所以，我们比我们需要的少了一个，所以我们需要在 mid - low 或 high - mid 中添加一个，但是哪一个？好吧，我们为两者制作表格并与我们的第一个表格进行比较。

如果我们将 1 添加到 mid - low 会怎样？

┏━━━━┯━━━━━━━┳━━━━━┳━━━━━┓
┃ low ╲ high ┃  4  ┃  5  ┃
┣━━━━━━┷━━━━━╋━━━━━╇━━━━━┫
┃     0      ┃ 3/2 │ 3/3 ┃
┣━━━━━━━━━━━━╉─────┼─────┨
┃     1      ┃ 2/2 │ 3/2 ┃
┗━━━━━━━━━━━━┻━━━━━┷━━━━━┛

如您所见，这与我们第一个表格中的可接受选项相匹配。如果我们将 1 添加到 high - mid 会怎样？

┏━━━━┯━━━━━━━┳━━━━━┳━━━━━┓
┃ low ╲ high ┃  4  ┃  5  ┃
┣━━━━━━┷━━━━━╋━━━━━╇━━━━━┫
┃     0      ┃ 2/3 │ 2/4 ┃
┣━━━━━━━━━━━━╉─────┼─────┨
┃     1      ┃ 1/3 │ 2/3 ┃
┗━━━━━━━━━━━━┻━━━━━┷━━━━━┛

如您所见，这是不平衡的。

所以，我们有 mid - low + 1 和 high - mid。

简单的解决方法

让它调试打印 lSize 和 rSize 值(System.err.printf("L:%d R:%d\n", lSize , rSize);) 将一个添加到 lSize，然后将一个添加到 rSize。尝试使用不同的数组大小，看看哪个最能平衡左侧和右侧。