这样的分区算法正确吗？

Question

我一直在看《破解编码面试》(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 2 3 3 5 6 4

左=4，右=4。退出

然而，我最后得到的数组是：

1 2 3 3 5 6 4

Answer 1

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

分区函数返回第二段开始的地方。在本例中，它从索引4开始。