java - 将快速排序修改为使用枢轴的快速排序 'median of three'

Question

我正在尝试将使用第一个元素作为基准的快速排序程序修改为使用三个中位数(第一个、最后一个和中间元素的中位数)作为基准的快速排序。然而，到目前为止，我的实现在测试时给出了 ArrayIndexOutOfBoundsException(s) 。我想我在这里遗漏了一些东西，但我就是不知道我错在哪里。非常感谢任何帮助和建议。

public class Sorts {

    private static void swap(int[] array, int index1, int index2) {
        // Precondition: index1 and index2 are >= 0 and < SIZE.
        //
        // Swaps the integers at locations index1 and index2 of the values array. 
        int temp = array[index1];
        array[index1] = array[index2];
        array[index2] = temp;
    }

    private static int medianOfThree(int[] array, int first, int last) {

        int mid = array[(first+last)/2];

        if (array[first] > array[mid]) {
            swap(array, first, mid);
        }

        if (array[first] > array[last]) {
            swap(array, first, last);
        }

        if (array[mid] > array[last]) {
            swap(array, mid, last);
        }
        swap(array, mid, last-1);
        return array[last-1];
    }

    private static int partition(int[] array, int first, int last, int median) {

        int pivot = array[last-1];
        int saveF = last-1;
        boolean onCorrectSide;

        first++;
        do {
            onCorrectSide = true;
            while (onCorrectSide) {           // move first toward last
                if (array[first] > pivot) {
                    onCorrectSide = false;
                }
                else {
                    first++;
                    onCorrectSide = (first <= last);
                }
            }

            onCorrectSide = (first <= last);
            while (onCorrectSide) {         // move last toward first
                if (array[last] <= pivot) {
                    onCorrectSide = false;
                }
                else {
                    last--;
                    onCorrectSide = (first <= last);
                }
            }

            if (first < last) {
                swap(array, first, last);
                first++;
                last--;
            }
        } while (first <= last);

        swap(array, saveF, last);
        return last;
    }


    private static void quickSort(int[] array, int first, int last) {

        if (first < last) {
            int pivot;

            int median = medianOfThree(array, first, last); 
            pivot = partition(array, first, last, median);

            // values[first]..values[splitPoint - 1] <= pivot
            // values[splitPoint] = pivot
            // values[splitPoint+1]..values[last] > pivot

            quickSort(array, first, pivot - 1);
            quickSort(array, pivot + 1, last);
        }
    }


    public static void quickSort(int[] array) {
        quickSort(array, 0, array.length-1);
    }
}

Answer 1

您没有以正确的方式使用变量:

 int mid = array[first+last/2];

给出数组中间的值，但不是数组的偏移量(索引)。但是您在方法调用中使用 mid 作为索引变量:

swap(array, first, mid);