快速排序算法不起作用

Question

我試圖實現這種快速排序算法，但即使它編譯正確，我得到一個ArrayIndexOutOfBoundsException

public class MyQuickSort { 
    private int array[]; 
    private int length; 

    public void sort(int[] inputArr) { 
    if (inputArr == null || inputArr.length == 0) 
     return; 

    this.array = inputArr; 
    length = inputArr.length; 
    quickSort(0, length-1); 
    } 

    private void quickSort(int lowerIndex, int higherIndex) { 
    int i = lowerIndex; 
    int j = higherIndex; 

    int pivot = array[lowerIndex+(higherIndex-lowerIndex)/2]; 
    while (i<=j) { 
     while (array[i] < pivot) { 
     i++; 
     } 
     while (array[j] > pivot) { 
     j--; 
     } 
     if (i <= j) { 
     exchangeNumbers(i, j); 
     i++; 
     j++; 
     } 
    } 

    if (lowerIndex < j) 
     quickSort(lowerIndex,j); 
    if (j <higherIndex) 
     quickSort(i, higherIndex); 
    } 

    private void exchangeNumbers(int i, int j) { 
    int temp = array[i]; 
    array[i] = array[j]; 
    array[j] = temp; 
    } 

    public static void main(String a[]) { 
    MyQuickSort sorter = new MyQuickSort(); 
    int[] input = {10,9,8,7,6,5,4,3,2,1}; 
    sorter.sort(input); 
    for(int i:input) 
     System.out.println(i); 
    } 
} 

這裏是例外：

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 10 
    at MyQuickSort.quickSort(MyQuickSort.java:23) 
    at MyQuickSort.sort(MyQuickSort.java:11) 
    at MyQuickSort.main(MyQuickSort.java:48) 

Answer 1

大概j在這裏超出範圍。

if (i <= j) { 
    exchangeNumbers(i, j); 
    i++; 
    j++; 
} 

Answer 2

後：

int pivot = array[lowerIndex+(higherIndex-lowerIndex)/2]; 

pivot現在6

是後：

while (array[j] > pivot) { 
    j--; 
} 

array[j]是1，所以這個循環永遠不會執行。

然後，因爲i=0和j=9，i<=j，所以程序調用j++;，所以j現在是10。然後，lowerIndex < j（因爲0<10），讓你再次調用該函數，用higherIndex=10，這會導致你的Exception。

Answer 3

更換行：

if (j <higherIndex) 

有：

if (i <higherIndex)