2017-09-16 91 views
0

我有一些問題java.lang.ArrayIndexOutOfBoundsException:10, 如果我設置1而不是0 - 我將有排序的數組與未排序的第一個元素,如果我設置0 - 我有錯誤 public void quicksort() { // Recursion quicksort(0, counter - 1); }快速排序麻煩java.lang.ArrayIndexOutOfBoundsException:10

這裏是我的代碼

public class Main { 
private static int comparations = 0; 
private static int swaps = 0; 
int[] array; 
int[] a; 
int counter = 0; 
int size; 

public void qwe() throws IOException { 
    Scanner scan = new Scanner(new File("input.txt")); //provide file name from outside 
    while(scan.hasNextInt()) 
    { 
     counter++; 
     scan.nextInt(); 
    } 
    System.out.println(counter); 
    Scanner scan2 = new Scanner(new File("input.txt")); 
    a = new int[counter]; 
    for(int i=0;i<counter;i++) 
    { 
     a[i]=scan2.nextInt(); //fill the array with the integers 
    } 
} 



public int partition(int p, int q) { 
    int i = p; 
    int j = q + 1; 
    // Get the pivot element from the middle of the list 
    int pivot = a[p]; 
    // Divide into two lists 
    do { 
     // If the current value from the left list is smaller then the pivot 
     // element then get the next element from the left list 
     do { 
      i++;// As we not get we can increase i 
     } while (a[i] < pivot); 
     // If the current value from the right list is larger then the pivot 
     // element then get the next element from the right list 
     do { 
      j--;// As we not get we can increase j 
     } while (a[j] > pivot); 
     // If we have found a values in the left list which is larger then 
     // the pivot element and if we have found a value in the right list 
     // which is smaller then the pivot element then we exchange the 
     // values. 
     if (i < j) { 
      swap(i, j); 
     } 

    } while (i < j); 
    // swap the pivot element and j th element 
    swap(p, j); 

    return j; 
} 

private void swap(int p, int j) { 
    // exchange the elements 
    int temp = a[p]; 
    a[p] = a[j]; 
    a[j] = temp; 
    swaps++; 
} 

public void quicksort() { 
    // Recursion 
    quicksort(0, counter - 1); 
} 

public void quicksort(int p, int q) { 
    int j; 
    if (p < q) { 
     // Divide into two lists 
     j = partition(p, q); 
     // Recursion 
     quicksort(p, j - 1); 
     quicksort(j + 1, q); 
    } 
    comparations++; 

} 

public void print() { 
    // print the elements of array 
    for (int i = 0; i < counter; i++) { 
     System.out.print(a[i] + ","); 
    } 
    System.out.println(); 

} 

public static void main(String args[]) throws IOException { 
    Main q = new Main(); 
    q.qwe(); 
    System.out.println("Before Sort <<<<<<<<<<<<<<<<<<<<<"); 
    q.print(); 
    q.quicksort(); 
    System.out.println("After Sort > > > > > > > > > > > >"); 
    q.print(); 
    System.out.println("Comparisons: " + comparations); 
    System.out.println("Swaps: " + swaps); 

} 
} 
+0

什麼的代碼行產生異常? – 4castle

回答

0

使用條件劃分方法

while(a[i] < pivot && i<q) 

,而不是

while(a[i] < pivot) 

,因爲你必須停止搜索比pivot大值,當你達到在年底

0

我認爲你必須避免do{...} while和使用while代替。

喜歡的東西:

public int partition(int p, int q) { 
    int i = p; 
    int j = q + 1; 
    // Get the pivot element from the middle of the list 
    int pivot = a[p]; 
    // Divide into two lists 
    while (i < j) { 
     // If the current value from the left list is smaller then the pivot 
     // element then get the next element from the left list 
     while (a[i] < pivot) { 
      i++;// As we not get we can increase i 
     } 
     // If the current value from the right list is larger then the pivot 
     // element then get the next element from the right list 
     while (a[j] > pivot) { 
      j--;// As we not get we can increase j 
     } 
     // If we have found a values in the left list which is larger then 
     // the pivot element and if we have found a value in the right list 
     // which is smaller then the pivot element then we exchange the 
     // values. 
     if (i < j) { 
      swap(i, j); 
     } 

    } 
    // swap the pivot element and j th element 
    swap(p, j); 

    return j; 
} 
0

我懷疑你的partition代碼是不正確的。因爲互換應該根據價值而不是指數進行。

if (i < j) { 
    swap(i, j); 
} 

Partitioning:重新排序所述陣列,使得具有小於落入樞軸前樞軸值 所有元素,而具有比跟從它樞軸更大 值的所有元素(等於無論哪種方式,值都可以變爲 )。在分區之後,該樞軸位於其最終的 位置。這被稱爲分區操作。

此外,爲什麼你讀兩次相同的文件不能得到相同循環中的元素和元素的數量?