合并排序中的子数组大小
我很难理解合并排序中子数组的大小。在以下代码中：
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大小的整个示例数组。如果我暂时不碰mergesort，我就忘了在哪里添加+1。还有更容易记住这一点的方法吗？谢谢。
回答 2
Stack Overflow用户
发布于 2018-10-16 21:06:32
溢出错误
首先，您不应该添加然后再划分索引。如果数组非常大，并且接近数组的末尾，则如果low和high索引溢出Integer.MAX_VALUE，则它们可以加为负数。然后，除以两，就会给出一个负值，而不是你所期望的正值。
这是一篇关于这个问题的谷歌博客文章。在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中添加一个，但是哪一个呢？嗯，我们为这两个人做桌子，并与我们的第一张桌子进行比较。
如果我们将一个添加到mid - low中，会发生什么？
┏━━━━┯━━━━━━━┳━━━━━┳━━━━━┓
┃ low ╲ high ┃ 4 ┃ 5 ┃
┣━━━━━━┷━━━━━╋━━━━━╇━━━━━┫
┃ 0 ┃ 3/2 │ 3/3 ┃
┣━━━━━━━━━━━━╉─────┼─────┨
┃ 1 ┃ 2/2 │ 3/2 ┃
┗━━━━━━━━━━━━┻━━━━━┷━━━━━┛如您所见，这与我们第一个表中可接受的选项相匹配。如果我们将一个添加到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中。尝试使用不同的数组大小，看看哪一种最能平衡左右两面。
Stack Overflow用户
发布于 2018-10-16 20:26:03
下面是一个例子。假设列表包含10个元素。以下是列表中的索引
0 1 2 3 4 5 6 7 8
现在，列表必须被分成两半，每一半递归排序-0 1 2 3 4在一半，5 6 7 8 9在另一半。所以上半场必须在4点停止，下半场必须在5点开始，9点结束。
如果你计算中途点mid = (9 + 0) / 2，它应该是4.5，但是由于这是整数数学，它被截断(不是四舍五入，截断)到4。所以你使用mid (4)作为上半部分的结尾，mid + 1 (5)作为下半部分的开始。
我希望这能让事情更清楚。
https://stackoverflow.com/questions/52843362
复制相似问题
腾讯云开发者
