迭代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合併排序

回答

相關問題