algorithm - 有人可以向我解释这个版本的快速排序(在中间选择枢轴)吗？

Question

我最近重温了快速排序。我过去常常通过从列表中选择最后一项或第一项来进行数据透视。然而，另一个我遇到了这个片段，其中从中间选择了枢轴。我知道枢轴的计算方式只会影响算法的性能。但我就是无法理解这种分区算法。

我想我理解分区算法的问题是，我认为它应该使结果数组像这样，所有小于主元的项目都向左移动，所有大于主元的项目都向左移动正确的。然而，这种分区算法并不总是能做到这一点。

private static void quickSort (int[] array, int left, int right) {
    int index = partition(array, left, right);

    //Sort left half
    if (left < index - 1)
        quickSort(array, left, index - 1);

    //Sort right half
    if (index < right)
        quickSort(array, index , right);
}

private static int partition (int array[], int left, int right) {
    int pivot = array[(left + right) / 2]; //Pick pivot point
    while (left <= right) {
        //Find element on left that should be on right
        while (array[left] < pivot)
            left++;

        //Find element on right that should be on left
        while (array[right] > pivot)
            right--;

        //Swap elements and move left and right indices
        if (left <= right) {
            int temp = array[left];
            array[left] = array[right];
            array[right] = temp;
            left++;
            right--;
        }
    }
    return left;
}

如果我给分区算法一个数组[1,0,-1,3,5,10,-5]，则主元将为3，但是分区后数组为 [ 1, 0, -1, -5, 5, 10, 3 ]。我只是无法理解它，因为它看起来不像分区在做任何有意义的事情。它没有将数组分成两半。

Answer 1

代码是 Hoare 分区方案的变体，其中每个分区步骤都会导致所有元素 < pivot 位于所有元素的左侧 > pivot，但是元素 == pivot，包括 pivot 本身，可以在左侧的任何位置结束或右分区，具体取决于数据模式。这就是递归调用使用 index-1 和 index 的原因，因为返回的索引不对应于 pivot，所以它不能从递归调用中排除。

在示例情况下，在第一个分区步骤中，左侧前进到 3，因为 array[{0,1,2}] < pivot，右侧没有改变，因为 array[{6}] 不是 >枢轴，导致交换(array[3]，array[6])，设置 array[3] = -5 和 array[6] = 3(枢轴)。