QuickSort QuickSort java.lang.ArrayIndexOutOfBoundsException: 10

Question

我在java.lang.ArrayIndexOutOfBoundsException: 10中遇到了一些问题，如果我设置了1而不是0-我将使用未排序的第一个元素排序数组，如果我设置为0-我有错误public void quicksort() { // Recursion quicksort(0, counter - 1); }。

这是我所有的代码

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);

}
}

Answer 1

在分区方法中使用条件

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

而不是

while(a[i] < pivot)

因为当你到达终点时，你必须停止寻找比支点更大的价值。

Answer 2

我认为您必须避免使用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;
}

Answer 3

我怀疑你的partition代码不正确。因为掉期应该基于价值而不是指数。

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

分区：重新排序数组，这样所有值小于的元素都会出现在支点之前，而值大于的所有元素都会出现在它之后(等量值都可以)。在此分区之后，枢轴处于其最后位置。这称为分区操作。

另外，为什么要读取同一文件两次--不能获得相同循环中的元素和元素的数量？