快速排序實現中的ArrayIndexOutofBound

Question

我想我的代碼應該可以工作，但它會在排序，分區和主要方法中拋出ArrayIndexOutofBounds異常。

我在哪裏錯了？

下面是代碼：

import java.util.Scanner; 

public class QuickSort 
{ 
public void sort(int a[], int low, int high) 
{ 

    if(low < high) 
    { 
     int q = partition(a, low, high); 
     sort(a, low, q-1); 
     sort(a, q+1, high); 
    } 
} 
public int partition(int a[], int low, int high) 
{ 
    int pivot=a[high]; 
    int i= (low-1); 
    for(int j=low; j<=high-1 ;j++) 
    { 
     if (a[j] <= pivot) 
     { 
      i++; 
      exchange(a[i], a[j]); 
     } 
    } 
    exchange(a[i+1], a[high]); 
    return i+1; 
} 
public void exchange(int v1,int v2) 
{ 
    int var1=v1; 
    int var2=v2; 
    var1 = var1 + var2; 
    var2 = var1 - var2; 
    var1 = var1 - var2; 
    //System.out.println(var1); 
    //System.out.println(var2); 
} 
public void printArr(int a[]) 
{ 
    int n=a.length; 
    System.out.println("SORTED ARRAY"); 
    System.out.println("-------------------------------------------"); 
    for(int i=0;i<n;i++) 
    { 
     System.out.print(a[i]); 
     System.out.print("\t"); 
    } 
} 

public static void main(String[] args) { 
    Scanner sc= new Scanner(System.in); 
    QuickSort obj = new QuickSort(); 
    // TODO Auto-generated method stub 

    System.out.println("Enter the no of elements in array"); 
    int n= sc.nextInt(); 
    int arr[] = new int[n]; 
    System.out.println("Enter the elements of array"); 
    for(int i=1;i<=n;i++) 
     { 
      arr[i]=sc.nextInt(); 
     } 


    obj.sort(arr, 1 , arr.length); 
    obj.printArr(arr); 

    sc.close(); 
} 
} 

這些都是在線程 「主」 java.lang.ArrayIndexOutOfBoundsException在Eclipse

異常的誤差：2
在快速排序。分區（QuickSort.java:17）
at QuickSort.sort（QuickSort.java:10）
在QuickSort.main（QuickSort.java:67）

Answer 1

您從main與arr.length爲high參數，它傳遞給partition打電話來sort。

在partition你做

int pivot = a[high]; 

這實際上是在Array

int pivot = a[a.length]; 

索引是從0到array size - 1，那是什麼導致ArrayIndexOutOfBoundsException。

在main

obj.sort(arr, 1 , arr.length); 

更改爲

obj.sort(arr, 1 , arr.length - 1); 

Answer 2

你的代碼有幾個錯誤：

1. 你用你的數組作爲猶如從1索引長度。在Java中，第一個元素位於[0] -cell中，最後一個位於[length-1] -cell中

2. 您的交換方法不起作用：您正在交換局部變量。在Java中，如果您調用兩個整數的方法，該方法會複製這些變量的值作爲輸入，並且您在該方法內進行的任何修改都不會影響原始變量。解決方案：將該數組作爲方法的輸入，並使用要交換的兩個索引。

3. 如果兩個變量實際上是相同的，那麼這種交換（在1 ...內部添加兩個變量）不起作用。您需要過濾該案例。 （該交換中使用的第三可變不需要此濾波器）

作爲設計選擇，寫上陣列方法時，參數（INT []數組，從int，int值）通常在'從'的情況下是包含性的，在'到'的情況下是排他性的。我也修改了你的代碼以適應這個規範。

固定所有這些，你得到這個代碼，我自己的電腦上運行correcty：（一標有「//有」意見修改）

import java.util.Scanner; 

public class QuickSort { 
public void sort(int a[], int low, int high) { 

    if (low < high - 1) { 
     int q = partition(a, low, high); 
     sort(a, low, q);// There 
     sort(a, q + 1, high);// There 
    } 
} 

public int partition(int a[], int low, int high) { 
    int pivot = a[high - 1]; 
    int i = (low - 1); 
    for (int j = low; j < high - 1; j++) { 
     if (a[j] <= pivot) { 
      i++; 
      exchange(a, i, j); 
     } 
    } 
    exchange(a, i + 1, high - 1); // There 
    return i + 1; 
} 

public void exchange(int[] tab, int i1, int i2) // There 
{ 
    if (i1 != i2) { 
     tab[i1] = tab[i1] + tab[i2]; 
     tab[i2] = tab[i1] - tab[i2]; 
     tab[i1] = tab[i1] - tab[i2]; 
    } 
    // System.out.println(tab[i1]); 
    // System.out.println(tab[i2]); 
} 

public void printArr(int a[]) { 
    int n = a.length; 
    System.out.println("SORTED ARRAY"); 
    System.out.println("-------------------------------------------"); 
    for (int i = 0; i < n; i++) { 
     System.out.print(a[i]); 
     System.out.print("\t"); 
    } 
} 

public static void main(String[] args) { 
    Scanner sc = new Scanner(System.in); 
    QuickSort obj = new QuickSort(); 
    // TODO Auto-generated method stub 

    System.out.println("Enter the no of elements in array"); 
    int n = sc.nextInt(); 
    int arr[] = new int[n]; 
    System.out.println("Enter the elements of array"); 
    for (int i = 0; i < n; i++) // There 
    { 
     arr[i] = sc.nextInt(); // There 
    } 

    obj.sort(arr, 0, arr.length); // There 
    obj.printArr(arr); 

    sc.close(); 
} 
}