我用 firstHalf 和 secondHalf 方法做了一个 MergeSort 方法;索引 0 ~ middle，

Question

public static void mergeSort(int[] data) {
int[] left = firstHalf(data);
int[] right = secondHalf(data);
if (data.length > 1) {
mergeSort(left);
mergeSort(right);
merge(data, left, right);  
} 
}
public static void merge(int[] data, int[] left, int[] right) {    
int tempArraySize = data.length;
int mergedNumbers[] = new int[tempArraySize]; //Temp array to take the sorted array
int mergePos;
int leftPos;
int rightPos;
int middle = data.length / 2;
mergePos = 0;
leftPos = 0;     // 0 index                
rightPos = middle + 1; //j is middle index
while (leftPos <= middle && rightPos <= data.length - 1) {
if (left[leftPos] < right[rightPos]) {
mergedNumbers[mergePos] = left[leftPos];
leftPos++;
} else {
mergedNumbers[mergePos] = right[rightPos];
rightPos++;
}
mergePos++;
}
// when the right half array finishes sorting
while (leftPos <= middle) {
mergedNumbers[mergePos] = left[leftPos];
leftPos++;
mergePos++;
}
// when the left half array finishes sorting
while (rightPos <= data.length - 1) {
mergedNumbers[mergePos] = right[rightPos];
rightPos++;
mergePos++;
}
// give value to the original array
for (mergePos = 0; mergePos < tempArraySize; ++mergePos) {
data[leftPos + mergePos] = mergedNumbers[mergePos];
}
}
public static int[] firstHalf(int[] data) {
int[] tempFirst = new int[(data.length / 2) + 1];
for (int i = 0; i <= data.length / 2; i++) {
tempFirst[i] = data[i];
}
return tempFirst;
}
public static int[] secondHalf(int[] data) {
int[] tempSecond = new int[(data.length / 2) + 1];
for (int i = (data.length / 2) + 1; i < data.length; i++) { // Middle to the end
for (int j = 0; j <= data.length / 2; j++) {
tempSecond[j] = data[i];
}
}
return tempSecond;
}

这是我做的。 我的mergeSort方法出错java.lang.StackOverflowError我犯了什么错误？ 我做了firstHalf和secondHalf方法来获取索引0~middle和middle+1~end。 这些方法是为了从原始的"数据"数组中获取值。merge方法与常用MergeSort代码相同。 我是否必须在mergeSort方法中构建基本案例？

Answer 1

使用这种方法，返回合并的数组更简单。对临时数组进行一次性分配，并使用索引在两个数组之间合并数据，而不是创建临时数组和复制数据，会更快。注释中注明的修复。

public static int[] mergeSort(int[] data) {         // fix
int[] left = firstHalf(data);
int[] right = secondHalf(data);
if(data.length < 2)                             // change
return data;                                // fix
left = mergeSort(left);                        // fix
right = mergeSort(right);                      // fix
return merge(left, right);                     // fix
}
public static int[] merge(int[] left, int[] right) {    // fix
int mergedNumbers [] = new int[left.length+right.length];   // fix
int mergePos = 0;                               // fix
int leftPos = 0;                                // fix
int rightPos = 0;                               // fix
while (leftPos < left.length && rightPos < right.length) {  // fix
if (left[leftPos] < right[rightPos]) {
mergedNumbers[mergePos] = left[leftPos];
leftPos++;
} else {
mergedNumbers[mergePos] = right[rightPos];
rightPos++;
}
mergePos++;
}
while (leftPos < left.length) {                 // fix
mergedNumbers[mergePos] = left[leftPos];
leftPos++;
mergePos++;
}
while (rightPos < right.length) {               // fix
mergedNumbers[mergePos] = right[rightPos];
rightPos++;
mergePos++;
}
return mergedNumbers;                           // fix
}
public static int[] firstHalf(int[] data) {
int j = (data.length/2);                        // fix
int[] tempFirst = new int[j];                   // fix      
for(int i = 0; i < tempFirst.length; i++)       // fix
tempFirst[i] = data[i];
return tempFirst;
}
public static int[] secondHalf(int[] data) {
int j = (data.length/2);                        // fix
int[] tempSecond = new int[data.length-j];      // fix
for(int i = 0; i < tempSecond.length; i++)      // fix
tempSecond[i] = data[i+j];                  // fix
return tempSecond;
}

维基文章对自上而下的合并排序有一个优化的方法：

https://en.wikipedia.org/wiki/Merge_sort#Top-down_implementation

Answer 2

代码中的问题来自指定包含边界的范围的混乱约定。相反，您应该考虑排除上限：这将避免所包含的约定所需的大量+1/-1调整，其中一些在您的代码中不一致：

• leftHalf创建一个长度为(data.length / 2) + 1的数组，包括偏移量mid = data.length / 2处的元素。这是merge方法所期望的，但不是最佳的，因为它会为偶数大小的数组制造不平衡的一半，并且更成问题的是为 2 元素数组返回 2 元素切片，这会导致无限递归并解释您得到的堆栈溢出异常。
• rightHalf还创建了一个长度为(data.length / 2) + 1的数组，这是不正确的，长度应array with lengthdata.length - ((data.length/2( + 1('，这将是 2 元素数组的空数组。
• 此外，rightHalf使用两个嵌套for循环从参数数组中复制值，这是不正确的。
• merge方法中，right数组中的索引范围不正确。

• 索引到data不正确data[leftPos + mergePos] = mergedNumbers[mergePos];它应该只是：

  data[mergePos] = mergedNumbers[mergePos];
  

下面是一个修改版本，具有不太容易出错的约定：

// sort elements in data in place
public static void mergeSort(int[] data) {
if (data.length > 1) {
int[] left = firstHalf(data);
int[] right = secondHalf(data);
mergeSort(left);
mergeSort(right);
merge(data, left, right);  
}
}
public static void merge(int[] data, int[] left, int[] right) {
int leftLength = left.length;
int rightLength = right.length;
int length = leftLength + rightLength;
int mergedNumbers[] = new int[length]; //Temp array to received the merged array
int leftPos = 0;
int rightPos = 0;
int mergePos = 0;
while (leftPos < leftLength && rightPos < rightLength) {
if (left[leftPos] <= right[rightPos]) {
mergedNumbers[mergePos] = left[leftPos];
leftPos++;
mergePos++;
} else {
mergedNumbers[mergePos] = right[rightPos];
rightPos++;
mergePos++;
}
}
// copy the remaining entries in the left half
while (leftPos < leftLength) {
mergedNumbers[mergePos] = left[leftPos];
leftPos++;
mergePos++;
}
// copy the remaining entries in the right half
while (rightPos < rightLength) {
mergedNumbers[mergePos] = right[rightPos];
rightPos++;
mergePos++;
}
// copy the values back to the original array
for (mergePos = 0; mergePos < length; mergePos++) {
data[mergePos] = mergedNumbers[mergePos];
}
}
public static int[] firstHalf(int[] data) {
int leftLength = data.length / 2;
int[] tempFirst = new int[leftLength];
for (int i = 0; i < leftLength; i++) {
tempFirst[i] = data[i];
}
return tempFirst;
}
public static int[] secondHalf(int[] data) {
int leftLength = data.length / 2;
int rightLength = data.length - leftLength;
int[] tempSecond = new int[rightLength];
for (int i = 0; i < rightLength; i++) {
tempSecond[i] = data[LeftLength + i];
}
return tempSecond;
}