这种分区算法是否正确？

Question

我一直在查看"Cracking the Coding Interview"一书中的分区功能(5e,第119页).我在下面复制了它:

int partition(int arr[], int left, int right){
    int pivot = arr[(left + right) /2 ]; // Pick pivot point
    while (left <= right) {
        // Find element on left that should be on right
        while (arr[left] < pivot) left++;
        // Find the element on right that should be on left
        while (arr[right] > pivot) right--;
        // Swap elements, and move left and right indicies
        if (left <= right) {
            swap(arr, left, right); // swaps elements
            left++;
            right--;
        }
    }
    return left;
}

给定这个数组:

1 2 3 4 5 6 3

这就是分区如何分阶段完成的

1. 4是枢轴值.left = 0,right = 6

2. left = 3,right = 6.交换.

   1 2 3 3 5 6 4

3. left = 4,right = 4.退出

但是,我最终得到的阵列:

1 2 3 3 5 6 4

没有分区4.我是否错误地遵循了步骤或算法是否错误？我已经仔细检查了我对算法的再现,并且我已经正确地复制了它.

另外,我不肯为什么分区左转,它是否会返回枢轴？

我理解维基百科对分区和快速排序的实现,但我试图围绕这里发生的事情.

Answer 1

分区的目标是将数组分成两段。第一段包含元素 [1,2,3,3]。所有这些值都小于或等于四。第二段包含元素 [5,6,4]。所有这些值都大于或等于四。

分区函数返回第二段开始的位置。在这种情况下，它从索引 4 开始。