java - 随机枢轴无法快速排序

Question

我无法理解这个partition 方法。使用随机 pivot 似乎不起作用，只有当我使用其中一个作为 pivot 时它似乎才有效:

• arr[left]
• arr[右 - 1]
• arr[(left + right)/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() 方法返回 left。

Answer 1

快速排序中的枢轴应该从被划分的子数组的元素中选择。因此它必须是arr[i]这样 i介于 left 之间和 right .选择arr[1]如果 left > 1 则无法工作或 right < 1 .

至于返回left - partition交换 left 范围内的数组元素至 right这样在完成后，left 中的所有元素(原来的left传递给方法)到left方法返回的 - 1 小于 left 中的所有元素方法返回原始right传递给方法。这允许您对两个分区中的每一个分区进行快速排序的递归调用。

该方法可以返回right相反，这将需要对实现进行轻微更改:

而不是调用

    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);
    }