就地快速排序w/最后一个元素枢轴

Question

我正试图实现就地快速排序，最后一个元素作为我的枢轴。下面是我的代码

public static void main(String[] args){
        int[] input = {3,2,4,6,10,1,9,7,5};
        quickSort(input, 0, input.length-1);
    }
    public static void swap(int[] array, int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
    public static int partition(int arr[], int left, int right) {
        int pivot = arr[right];
        int high = right-1;
        while(left < high){
            while(arr[left] < pivot){
                left++;
            }
            while(arr[high] > pivot){
                high--;
            }
            swap(arr,left, high);
            left++;
            high--;
        }
        swap(arr, left, pivot);
        System.out.println(Arrays.toString(arr));
        return left;
    }
    public static void quickSort(int arr[], int left, int right) {
        int index = partition(arr, left, right);
        quickSort(arr, left, index - 1);
        quickSort(arr, index, right);
    }

由于某种原因，我的代码给了我一个IndexOutOfBounds异常，它没有准确地对数组进行排序。我不确定为什么我得到这个错误。

如果我理解正确的话，我们应该把最后一个元素作为支点。然后，将左指针向右迭代，直到找到一个大于枢轴的元素。在那之后，我们从右边做同样的事情(继续向左移动)，直到我们找到一个比主元小的元素。然后我们交换这些元素，继续做同样的事情。

最后，当左/右指针相同时，我们将中心值与枢轴值交换。

这是正确的思考方式吗?如果是，我的代码有什么错误?如有任何帮助，不胜感激

Answer 1

几个错误:

• 添加left < high检查到您的内环。

• 检查arr[high] >= pivot而不是arr[high] > pivot

• swap(arr, left, pivot);错误。你应该用位置来交换左和枢轴，而不是值。应该是swap(arr, left, right);

• 你应该在你的快速排序方法中检查left < right

当你修复了这些错误，你的代码应该是这样的:

    public static void main(String[] args){
        int[] input = {3,2,4,6,10,1,9,7,5};
        quickSort(input, 0, input.length-1);
    }
    public static void swap(int[] array, int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
    public static int partition(int arr[], int left, int right) {
        int pivot = arr[right];
        int high = right;
        while(left < high){
            while(left < high && arr[left] < pivot){
                left++;
            }
            while(left < high && arr[high] >= pivot){
                high--;
            }
            swap(arr,left, high);
        }
        swap(arr, left, right);
        System.out.println( Arrays.toString(arr));
        return left;
    }
    public 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, right);
        }
    }

Answer 2

假设最后一个数组元素是最小的元素，跟踪这段代码。调整high的循环将持续递减high，因为每个数组元素都比枢轴大，所以最终high将从数组的前面下降，导致你的越界访问。

要解决这个问题，在循环中添加另一个检查，以确保您没有高和左交叉。然后，您可能需要添加一些额外的逻辑，以便将其作为特殊情况处理。