快速排序 Java 。 ArrayIndexoutofBoundsException异常

Question

我想快速排序 algoritm.I 正在学习快速排序算法。

Out: ArrayIndexoutofBoundsException error.I 找不到错误。

我不好English.Sorry。我该如何解决这个问题？

public class Quickort {
static int partition(int arr[],int left,int right){
    int i=left;
    int j=right;
    int tmp;    
    int pivot=(left/right)/2;
    while(i<=j){
        while(arr[i]<pivot)
            i++;
        while(arr[j]>pivot)
            j--;

        if(i<=j){
        tmp=arr[i];
        arr[i]=arr[j];
        arr[j]=tmp;
        i++;
        j--;
        }
     }
    return i;
}
static void quicksort(int arr[],int left,int right){
int index=partition(arr,left,right);

if(left<index-1)
    quicksort(arr, left, index-1);
if(index<right)
quicksort(arr, index, right);


}


public static void main(String[] args) {
    int [] arr={8,4,1,7,9,4,3,2,5};
    quicksort(arr,0,arr.length-1);


}

}

Answer 1

将int pivot=(left/right)/2;更改为int pivot=(left+right)/2;

Answer 2

根据你的代码

  int pivot=(left/right)/2;

您将获得零的枢轴。因为这个循环

while(arr[j]>pivot)
        j--;

j 变为 -1 并且由于数组不包含它，它抛出 ArrayIndexoutofBoundsException

Answer 3

枢轴变量的值应该是数组中的一个元素 (int pivot = arr[right];)。

试试这个：

static int partition(int arr[], int left, int right) {
    int pivot = arr[right];
    int i = left - 1;
    int tmp;
    for (int j = left; j <= right; j++) {
        if (arr[j] <= pivot) {
            i++;
            tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }
    }
    return i;
}

static void quicksort(int arr[], int left, int right) {
    if(left < right){
        int index = partition(arr, left, right);
        quicksort(arr, left, index - 1);
        quicksort(arr, index + 1, right);
    }
}

快速排序 Java 。 ArrayIndexoutofBoundsException异常

Quick Sort Java . ArrayIndexoutofBoundsException

java

algorithm

quicksort

data-structures