我将此合并排序算法实现到 java 中，但没有用

Question

这是我的算法入门课程，我了解算法并且可以设计它们，但这是我第一次尝试将它应用到 java 代码中，请告诉我我做错了什么使其无法正常工作的代码 I'm trying to apply this algorithm , this is the rest of the algorithm

这是我的主要虚空：

int[] A = { 5, 2, 4, 7, 1, 3, 2, 6 };
int p = 1;
int r = A.length;

Main obi = new Main ();
obi.mergeSort (A, p, r);

我的第一个函数：


public void mergeSort (int[]A, int p, int r) {

    if (p < r){
        int q = (p + r) / 2;
        mergeSort (A, p, q);
        mergeSort (A, q + 1, r);
        merge (A, p, q, r);
    }

}

我的第二个功能：

public void merge (int[]A, int p, int q, int r) {

    int n1 = q - p + 1;
    int n2 = r - q;

    int L[] = new int[n1];
    int R[] = new int[n2];

    for (int i = 0; i < n1; i++){
        L[i] = A[p + i - 1];
        
    }
    
    for (int j = 0; j < n2; j++){
        R[j] = A[q + j];
        
    }
    
    int i = 0;
    int j = 0;

    for (int k = p - 1; k < r; k++){
        if (L[i] <= R[j]){
            A[k] = L[i];
            i = i + 1;
            
        } else {
            A[k] = R[j];
            j = j + 1;
            
        }
    }

}

这是我收到的错误消息：

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 1
    at Main.merge(Main.java:44)
    at Main.mergeSort(Main.java:19)
    at Main.mergeSort(Main.java:17)
    at Main.mergeSort(Main.java:17)
    at Main.main(Main.java:10)

我试着让 L[] 和 R[] 的长度分别为 n1+1 和 n2+1 但没有用。

Answer 1

L 或 R 首先完成。

for (int k = p - 1; k < r; k++){
    if (L[i] <= R[j]){
        A[k] = L[i];
        i = i + 1;   
    } else {
        A[k] = R[j];
        j = j + 1;   
    }
}

假设 L 先完成，然后 i 变为 L.length+1，这样当下一次迭代发生时，L[i] 无效，因为它已经结束了。

Answer 2

您的代码中存在多个问题：

参数 r 和 q 应该是切片中第一个元素的索引，因此 main() 中的 int p = 0; 而不是 1，并且索引超过切片中的最后一个元素，因此正确 int r = A.length;

有了这个约定，就不需要在 merge 和 mergeSort 方法中进行混乱和容易出错的 +1/-1 调整。

此外，merge中的合并循环应该被修改，以避免在相应索引达到数组长度时访问L[i]或R[j]。

这是修改后的版本：

    ...
    int[] A = { 5, 2, 4, 7, 1, 3, 2, 6 };
    int p = 0;
    int r = A.length;

    Main obi = new Main();
    obi.mergeSort(A, p, r);
    ...

public void mergeSort(int[]A, int p, int r) {
    if (r - p > 1) {
        int q = p + (r - p) / 2;
        mergeSort(A, p, q);
        mergeSort(A, q, r);
        merge(A, p, q, r);
    }
}

public void merge(int[]A, int p, int q, int r) {
    int n1 = q - p;
    int n2 = r - q;

    int L[] = new int[n1];
    int R[] = new int[n2];

    for (int i = 0; i < n1; i++) {
        L[i] = A[p + i];
    }
    
    for (int j = 0; j < n2; j++) {
        R[j] = A[q + j];
    }
    
    int i = 0;
    int j = 0;

    for (int k = p; k < r; k++) {
        if (i < n1 && (j >= n2 || L[i] <= R[j])) {
            A[k] = L[i];
            i = i + 1;
        } else {
            A[k] = R[j];
            j = j + 1;
        }
    }
}

请注意，merge 方法可以简化，因为下半部分的元素在移动到最终位置之前不会被覆盖，因此无需保存它们：

public void merge(int[]A, int p, int q, int r) {
    int n1 = q - p;
    int L[] = new int[n1];
    for (int i = 0; i < n1; i++) {
        L[i] = A[p + i];
    }
    
    int i = 0;
    int j = q;
    int k = p;

    while (i < n1) {
        if (j >= r || L[i] <= A[j])
            A[k++] = L[i++];
        else
            A[k++] = A[j++];
    }
}

我将此合并排序算法实现到 java 中，但没有用

I implemented this merge sort algorithm into java and it didn't work

java

arrays

algorithm

mergesort