-2

我试图解决这个插入排序问题（不是确切的插入排序）并编写了以下代码：

import java.util.*;
public class Solution {

    static void insertionSort(int[] ar,int n) {
        int key=ar[n];
        int temp;
        int j=1;
        for(int i=0;i<ar.length;i++){
              j++;
        }

        for(int i=j-1;i>=0;i--){
            temp=ar[i];
            if(temp>key)
            {
                ar[i+1]=temp;
                printArray(ar);
            }
            else{
                ar[i+1]=key;
                printArray(ar);
            }
        }
    }   

/* Tail starts here */

    static void printArray(int[] ar) {
        for(int n: ar){
            System.out.print(n+" ");
        }
        System.out.println("");
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] ar = new int[n];
        for(int i=0;i<n;i++){
            ar[i]=in.nextInt(); 
        }
       insertionSort(ar,n);
    }    
}

但是我收到了一个数组越界异常的错误，我不知道哪里出了问题。错误消息发布在下面。我应该如何解决这个问题？

线程“main”中的异常 java.lang.ArrayIndexOutOfBoundsException: 5 在 Solution.insertionSort(Solution.java:9) 在 Solution.main(Solution.java:49)

4

4 回答 4

2

正如布赖恩指出的那样，第一行是行不通的，因为你有

int key=ar[n];

并且n是ar.length（在这种情况下也使它变得多余）

使用调试器会显示错误，但我怀疑问题出在这里

ar[i+1]=temp;

我认为i是最后一个有效的参考。

顺便提一句

      int j=1;
      for(int i=0;i<ar.length;i++){
          j++;

      }

是相同的

int j = 1 + ar.length;

同样，这会使j或j-1太大而无法在数组中索引。

于 2013-08-20T18:03:16.417 回答
2

当您尝试访问不存在的位置时，会发生上面提到的 ArrayIndexOutOfBoundException。

您已通过您的 insertSort() 函数数组的大小。我认为您不需要 aj 变量。

通过您的实施：

j = ar.length + 1 = n + 1;

例如：

n = 5

ar =  3, 6, 2, 7, 3
      ^  ^  ^  ^  ^
index:0, 1, 2, 3, 4

j = n+1 = 6

当您从 i=j-1; 循环您的数组时

temp=ar[i];                     -> ar[5]
ar[i+1]=key; or ar[i+1]=temp;   -> ar[6]

您在上面尝试访问的两个位置都是非法的 - 因此出现错误

你的 for 循环应该是这样的：

for(int i=n-2; i>=0; i--)
于 2013-08-20T18:42:16.330 回答
0

首先，您能否将变量命名为“i”、“j”和“n”以外的名称？然后一旦你这样做了，在你的代码中使用一致的风格（你已经去掉了一些大括号而不是其他的？）。

然后，..一旦您可以轻松阅读代码，使用调试器，并找出您将在哪一行进行。您可能会发现这很有用： http: //docs.oracle.com/javase/7/docs/api/java/lang/ArrayIndexOutOfBoundsException.html

这是第 49 行。这意味着此时，您尝试访问数组中不存在的位置。您的数组当前大小为“n”（正确命名！）。您正试图在此处获得位置 n： 

int key=ar[n];

您拥有的数组从 0 到 n-1。例如，如果 n 为 5，则有 ar[0]、ar[1]、ar[2]、ar[3] 和 ar[4]。即 5 个位置，因此 ar[5]（或 ar[n]）不存在。

于 2013-08-20T18:08:22.813 回答
0

我找到了答案

 /* Head ends here */
 import java.util.*;
 public class Solution {

      static void insertionSort(int[] ar,int n) {

          int key=ar[n-1];
          int temp;
          int inserted=0;
          for(int i=ar.length-2;i>-1;i--){
              temp=ar[i];
              if(temp>key)
              {
                  ar[i+1]=temp;
                  printArray(ar);
              }
              else {
                  ar[i+1]=key;
                  inserted=1;
                  break;

              }

          }

          if(inserted==0){
          ar[0]=key;
          }

          printArray(ar);
   }   

   /* Tail starts here */

  static void printArray(int[] ar) {
     for(int n: ar){
        System.out.print(n+" ");
     }
       System.out.println("");
  }

  public static void main(String[] args) {
       Scanner in = new Scanner(System.in);
       int n = in.nextInt();
       int[] ar = new int[n];
       for(int i=0;i<n;i++){
          ar[i]=in.nextInt(); 
       }
       insertionSort(ar,n);
   }    
 }
于 2013-08-20T18:38:12.460 回答