java - 为什么我的分区算法返回 ArrayIndexOutOfBoundsException

Question

我一直在尝试学习 Java 中的算法，并一直在尝试实现 Hoares 分区，并且一直在查看多个示例，但是当我尝试在 intellij 中实现时，我遇到了这个错误:

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index -1 out of bounds for length 6
    at QuickSort.partitionSort(QuickSort.java:18)
    at QuickSort.quickSort(QuickSort.java:35)
    at QuickSort.main(QuickSort.java:52)

刚刚开始学习，不知道怎么解决

import java.io.*;

public class QuickSort {

    static int partitionSort(int[] arr, int h, int l) {
        int i = l - 1;
        int j = h + 1;

        int pivot = arr[l];

        while(true) {
            do {
                i++;
            } while(arr[i] < pivot);

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

            if (i >= j)
                return j;

            int tempArr = arr[i];
            arr[i] = arr[j];
            arr[j] = tempArr;

        }
    }

    static void quickSort(int[] arr, int l, int h) {

        if (l > h)
            return;

        int q = partitionSort(arr, l, h);

        quickSort(arr, l, q);
        quickSort(arr, q + 1, h);
    }


    static void pArray(int[] arr, int n) {
        for (int i = 0; i < n; i++) {
            System.out.print(" " + arr[i]);
            System.out.println();
        }
    }

    public static void main(String args[]) {
        int arr[] = {5, 8, 10, 3, 4, 1};
        int n = arr.length;
        quickSort(arr, 0, n - 1);
        System.out.println("Before sorting: " + arr);
        System.out.println("Sorted array: ");
        pArray(arr, n);
    }

}

Answer 1

partitionSort 的索引参数是相反的。我的 Java 版本也不允许 System.out.println("Sorted array: "+ arr);这应该在排序之前完成。您可能会考虑在 partitionSort 中使用中间值作为主元。

import java.io.*;                           // is this needed?

public class QuickSort {

    static int partitionSort(int[] arr, int l, int h) {   // fix, swap l and h
        int i = l - 1;
        int j = h + 1;

        int pivot = arr[l];    // might want to use int pivot = arr[l + (h-l)/2];

        while(true) {
            do {                       // could be while(arr[++i] < pivot);
                i++;
            } while(arr[i] < pivot);

            do {                       // could be while(arr[--j] > pivot);
                j--;
            } while(arr[j] > pivot);

            if (i >= j)
                return j;

            int tempArr = arr[i];tempArr
            arr[i] = arr[j];
            arr[j] = tempArr;

        }
    }

    static void quickSort(int[] arr, int l, int h) {

        if (l >= h)                         // fix, if l >= h, nothing to do
            return;

        int q = partitionSort(arr, l, h);

        quickSort(arr, l, q);
        quickSort(arr, q + 1, h);
    }

    static void pArray(int[] arr, int n) {
        for (int i = 0; i < n; i++) {
            System.out.print(" " + arr[i]);
            System.out.println();
        }
    }

    public static void main(String args[]) {
        int arr[] = {5, 8, 10, 3, 4, 1};
        int n = arr.length;
        System.out.println("Before sorting: ");  // changed
        pArray(arr, n);                          // changed
        quickSort(arr, 0, n - 1);
        System.out.println("Sorted array: ");
        pArray(arr, n);
    }
}