java - 我在实现 Java 合并排序时遇到问题

Question

public static void main(String[] args) {
    int[] test = {5,4,3,5,7,5,1,5,96};
    System.out.print("Before: ");
    printList(test);
    mergeSort(test, 1, test.length);
    //System.out.print("After:  ");
    //printList(test);
}

public static void printList(int[] test){
    for (int i= 0; i < test.length; i++){
        System.out.print(test[i] + " ");
    }
    System.out.println();
}

public static 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 = 1; i <= n1; i++){
        L[i] = A[p+i-1];
    }
    for (int j = 1; j <= n2; j++){
        R[j] = A[q+j];
    }
    int i = 1;
    int j = 1;

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

public static 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);
    }
}

我正在尝试在测试数组上实现合并排序，但我不确定为什么会收到 ArrayIndexOutOfBoundsException 错误。任务是更改合并排序代码，使其在搜索时不使用任何标记。

    Before: 5 4 3 5 7 5 1 5 96 
    Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 1
    at Lab1_2.merge(Lab1_2.java:28)
    at Lab1_2.mergeSort(Lab1_2.java:61)
    at Lab1_2.mergeSort(Lab1_2.java:59)
    at Lab1_2.mergeSort(Lab1_2.java:59)
    at Lab1_2.mergeSort(Lab1_2.java:59)
    at Lab1_2.main(Lab1_2.java:8)

这是我收到的错误消息。

Answer 1

您收到 ArrayIndexOutOfBoundsException 运行时异常，因为您尝试访问超出数组边界(限制)的数组。在 merge 方法中，您的语句如

 int[] L = new int[n1];

声明大小为 n1 的数组，您可以获取索引从 0 到 n-1 的元素。但您尝试将元素存储在索引 n1 处。这是不可能的，因为我们知道数组的元素从 0 到 size-1 (这里 size 是数组的长度)，这是原因之一。你在其他一些地方也有问题。因此，我编辑您的代码并希望以下代码对您有用。

/* package whatever; // don't place package name! */

import java.util.*;

import java.lang.*;

import java.io.*;


class Ideone
    {
    public static void main (String[] args) throws java.lang.Exception
    {
    // your code goes here
        int[] test = {5,4,3,5,7,5,1,5,96};
    System.out.print("Before: ");
    printList(test);
    mergeSort(test, 0, test.length-1);
    System.out.print("After:  ");
    printList(test);
}

public static void printList(int[] test){
for (int i= 0; i < test.length; i++){
    System.out.print(test[i] + " ");
}
System.out.println();
}

public static 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];
}
for (int j = 0; j < n2; j++){
    R[j] = A[q+j+1];
}
//int i = 0;
//int j = 0;

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

       int i = 0, j = 0;


    int k = p;
    while (i < n1 && j < n2)
    {
        if (L[i] <= R[j])
        {
            A[k] = L[i];
            i++;
        }
        else
        {
            A[k] = R[j];
            j++;
        }
        k++;
    }


    while (i < n1)
    {
        A[k] = L[i];
        i++;
        k++;
    }


    while (j < n2)
    {
        A[k] = R[j];
        j++;
        k++;
    }

}

public static 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);
}
}

}