我在理解此分区方法时遇到了麻烦.使用随机数据透视似乎无效,仅当我将其中之一用作数据透视似乎有效：

> arr [左]
> arr [右-1]
> arr [(左右)/ 2]

但是,我认为任何元素都应该起作用.当我将其更改为arr [1]之类的代码时,代码将停止工作…我是否对数据透视表有所误解？

这是partition()方法的代码：

public static int partition(int arr[], int left, int right) {
    // Pick a pivot point. Can be any element.
    int pivot = arr[(left + right) / 2]; 

    while (left <= right) {
        while (arr[left] < pivot) {
            left++;
        }

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

        if (left <= right) {
            swap(arr, left, right);
            left++;
            right--;
        }
    }

    return left;
}

这是完整的快速排序代码的链接：https://gist.github.com/anonymous/e1c74f2794ecb5b898ab

附带说明一下,我也不确定为什么我们要从partition()方法返回左端.

解决方法:

Quicksort中的支点应从要分区的子数组的元素中选择.因此,它必须为arr [i],以使i在左右之间.如果离开&gt ;,则无法选择arr [1]. 1或正确的< 1. 至于返回左-分区在从左到右的范围内执行数组元素的交换,这样,完成后,方法-1返回的从左(传递给该方法的原始左)到左的所有元素都较小比从方法返回的左边到传递给方法的原始右边的所有元素都多.这使您可以递归调用两个分区中的每个分区的quicksort. 该方法可以返回正确的结果,这需要对实现进行一些更改： 而不是打电话

    if (left < index - 1) {
        quickSort(arr, left, index - 1);
    }

    if (index < right) {
        quickSort(arr, index, right);
    }

分区后,您将打电话给

    if (left < index) {
        quickSort(arr, left, index);
    }

    if (index + 1 < right) {
        quickSort(arr, index + 1, right);
    }