java - 快速排序越界错误

Question

我正在尝试构建一个快速排序函数，该函数使用三个值的中位数作为基准，但我遇到了问题。我在第 56、66、35、34 和 84 行遇到越界错误，并且尝试更改此设置但无济于事。有什么想法吗？

public class MyQuickSort {

    private int array[];
    private int length;

    public void sort(int[] inputArr) {

        if (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;
        // calculate pivot number, I am taking pivot as middle index number
        int mid = array[(higherIndex-1)/2];
        // Divide into two arrays

        int pivot = findMedian(array, i, mid, j);
        swap(pivot, 0);

        while (i <= j) {
            /**
             * In each iteration, we will identify a number from left side which
             * is greater then the pivot value, and also we will identify a number
             * from right side which is less then the pivot value. Once the search
             * is done, then we exchange both numbers.
             */
            while (array[i] < mid) {
                i++;
            }
            while (array[j] > mid) {
                j--;
            }
            if (i <= j) {
                swap(i, j);
                //move index to next position on both sides
                i++;
                j--;
            }
        }
        // call quickSort() method recursively
        if (lowerIndex < j)
            quickSort(lowerIndex, j);
        if (i < higherIndex)
            quickSort(i, higherIndex);
    }

    public static int findMedian (int[] array, int a, int b, int c) {
        if ((array[a] > array[b] && array[a] < array[c]) || (array[a] > array[c] && array[a] < array[b])) {
            return a; 
        } else if ((array[b] > array[a] && array[b] < array[c]) || (array[b] > array[c] && array[b] < array[a])) {
            return b; 
        }
        return c; 
    }


    private void swap(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 = {24,2,45,20,56,75,2,56,99,53,12};
        sorter.sort(input);
        for(int i:input){
            System.out.print(i);
            System.out.print(" ");
        }
    }
}

Answer 1

问题在于变量“mid”既用作索引又用作值。函数 findMedian() 仅需要索引，而不需要数组中的值。

如果我将快速排序()更改为(请注意，这还包括 midIndex 的索引边界检查):

    private void quickSort(int lowerIndex, int higherIndex) {

        int i = lowerIndex;
        int j = higherIndex;
        // calculate pivot number, I am taking pivot as middle index number
        int midIndex = (higherIndex-1)/2;
        if (midIndex < lowerIndex) {
          midIndex = lowerIndex;
        }
        int mid = array[midIndex];
        // Divide into two arrays

        int pivot = findMedian(array, i, midIndex, j);
        swap(pivot, i);

        while (i <= j) {
            /**
             * In each iteration, we will identify a number from left side which
             * is greater then the pivot value, and also we will identify a number
             * from right side which is less then the pivot value. Once the search
             * is done, then we exchange both numbers.
             */
            while (array[i] < mid) {
                i++;
            }
            while (array[j] > mid) {
                j--;
            }
            if (i <= j) {
                swap(i, j);
                //move index to next position on both sides
                i++;
                j--;
            }
        }
        // call quickSort() method recursively
        if (lowerIndex < j)
            quickSort(lowerIndex, j);
        if (i < higherIndex)
            quickSort(i, higherIndex);
    }

我得到:

java MyQuickSort
2 2 12 20 24 45 53 56 56 75 99