迭代Java合并排序

我正在尝试为合并进行合并排序的迭代版本。我从网站上获得了合并排序方法，并且我研究了应该合并数组的方法。但是我不断收到IndexOutOfBounds异常。迭代Java合并排序

我一直在这个工作多个小时，我找不到错误。有人可以帮我找到解决办法吗？

到目前为止，我有这样的：

public static void MergeSort(int[] array) { 
    int current; 
    int leftStart; 
    int arraySize = array.length - 1; 
    for (current = 1; current <= arraySize; current = 2 * current) { 
     for (leftStart = 0; leftStart <= arraySize; leftStart += 2 * current) { 

      int mid = leftStart + current - 1; 
      int right = getMin(leftStart + 2 * current - 1, arraySize); 

      mergeArray(array, leftStart, mid, right); 
     } 

    } 

} 

public static void mergeArray(int[] array, int left, int mid, int right) { 

    int leftArraySize = mid - left + 1; 
    int rightArraySize = right - mid; 

    int[] leftArray = new int[leftArraySize]; 
    int[] rightArray = new int[rightArraySize]; 

    for (int i = 0; i < leftArraySize; i++) 
     leftArray[i] = array[left + i]; 

    for (int i = 0; i < rightArraySize; i++) 
     rightArray[i] = array[mid + 1 + i]; 

    int leftPtr = 0; 
    int rightPtr = 0; 
    int tempPtr = leftPtr; 

    while (leftPtr < leftArraySize && rightPtr < rightArraySize) { 

     if (leftArray[leftPtr] <= rightArray[rightPtr]) 
      array[tempPtr++] = leftArray[leftPtr++]; 

     else 
      array[tempPtr++] = rightArray[rightPtr++]; 
    } 

    while (leftPtr <= left) 
     array[tempPtr++] = leftArray[leftPtr++]; 

    while (rightPtr < right) 
     array[tempPtr++] = rightArray[rightPtr++]; 

} 

public static int getMin(int left, int right) { 
    if (left <= right) { 
     return left; 
    } else { 
     return right; 
    } 
}

任何形式的帮助将不胜感激！

谢谢！

来源

2016-11-22 Ronny Pacheco

您应该开始告诉我们错误的确切位置。这很容易实现，因为您知道这是一个无界限错误，您可以简单地在可能发生此类错误的所有点上使用调试器或系统消息。这是你的工作，而不是我们的。 – Aziuth

尝试一步一步理解算法和调试代码。 – shawn

试试这个代码执行成功：只有小的失误在mergeArray()方法：

array[tempPtr++] = leftArray[leftPtr++];

不要在阵列增加...... 更换

array[tempPtr] = leftArray [leftPtr]; 
     leftPtr++;

最终代码：比较我的代码你会得到它。

public static void MergeSort(int[] array) { 
int current; 
int leftStart; 
int arraySize = array.length; 
for (current = 1; current <= arraySize-1; current = 2 * current) { 
for (leftStart = 0; leftStart < arraySize-1; leftStart += 2 * current) { 

    int mid = leftStart + current - 1; 
    int right = getMin(leftStart + 2 * current - 1, arraySize-1); 

    mergeArray(array, leftStart, mid, right); 
}}} 

static void printArray(int A[]) 
{ 
int i; 
    for (i=0; i < A.length; i++) 
    System.out.println(A[i]); 
    } 

static void mergeArray(int array[], int left, int mid, int right) 
    { 
    int leftArraySize = mid - left + 1; 
int rightArraySize = right - mid; 

     int[] leftArray = new int[leftArraySize]; 
int[] rightArray = new int[rightArraySize]; 

for (int i = 0; i < leftArraySize ; i++) 
    leftArray [i] = array[left + i]; 
for (int j = 0; j < rightArraySize; j++) 
    rightArray[j] = array[mid + 1+ j]; 

    int leftPtr = 0; 
    int rightPtr = 0; 
    int tempPtr = left; 
while (leftPtr < leftArraySize && rightPtr < rightArraySize) 
{ 
    if (leftArray [leftPtr ] <= rightArray[rightPtr ]) 
    { 
     array[tempPtr] = leftArray [leftPtr]; 
     leftPtr++; 
    } 
    else 
    { 
     array[tempPtr] = rightArray[rightPtr]; 
     rightPtr++; 
    } 
    tempPtr++; 
} 

while (leftPtr < leftArraySize) 
{ 
    array[tempPtr++] = leftArray [leftPtr++]; 

    leftPtr++; 
    tempPtr++; 
} 

while (rightPtr < rightArraySize) 
{ 
    array[tempPtr++] = rightArray[rightPtr++]; 

    rightPtr++; 
    tempPtr++; 
} } 

    public static int getMin(int left, int right) { 
    if (left <= right) { 
return left; 
} else { 
    return right; 
}}

来源

2016-11-22 08:36:56

你在这个方法mergeArray（）做了一些错误.. –

如果你理解上面的答案接受它@Ronny Pacheco –

这不是一个答案。你没有解释原始程序错在哪里，因此没有任何东西被学习到。你不提供被盲目接受的代码。 – Aziuth

合并排序算法是一种经典的分而治之算法。

鸿沟问题成更小的子问题
通过递归调用征服。
结合的子问题的解决方案为一体的原问题

用于合并的伪代码：

C = output[length = n] 
A = 1st sorted array[n/2] 
B = 2st sorted array[n/2] 
i = 1 
j = 1 
for k = 1 to n 
    if A[i] < B[j] 
     C[k] = A[i] 
     i++ 
    else B[j]<A[i] 
     C[k] = B[j] 
     j++ 
end (ignores end cases)

所以你的源代码的问题是这一行：

array[tempPtr++] = leftArray[leftPtr++];

请变化到伪代码的逻辑：

if (leftArray [leftPtr ] <= rightArray[rightPtr ]) 
{ 
    array[tempPtr] = leftArray [leftPtr]; 
    leftPtr++; 
} 
else 
{ 
    array[tempPtr] = rightArray[rightPtr]; 
    rightPtr++; 
}

来源

2016-11-22 13:18:48 shawn

迭代Java合并排序

回答

相关问题