这个分区算法是否正确？

Question

我一直在研究《程序员面试金典》（第五版，第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是枢轴值。左边=0，右边=6

2. 左边=3，右边=6。交换。

   1 2 3 3 5 6 4

3. 左边=4，右边=4。退出

然而，我最终得到的数组：

1 2 3 3 5 6 4

分区的结果不是4。我是否跟错了步骤，还是算法有误？我已经仔细检查了算法的复制过程，并且正确地复制了它。

另外，我不确定为什么分区返回左侧，是返回枢轴吗？

我理解维基百科对于分区和快速排序的实现，但我正在努力理清楚这里发生了什么。

- oxuser

---

为什么你说它没有在4周围分区？你是期望4不移动吗？ - Vaughn Cato

在我上面的解决方案中，5和6仍然在4的左侧。这不意味着它还没有分区吗？ - oxuser

你能告诉我们 left 和 right 分别代表什么吗？ - LastStar007

@LastStar007 的 left 和 right 表示数组的起始和结束索引。这是一种原地分区。 - oxuser

我明白了。你知道这实际上不是快速排序算法吗？ - LastStar007

Answer 1

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

分割函数返回第二段开始的位置。在本例中，它从索引4开始。

- Vaughn Cato

---

但是按照算法，我得到了1 2 3 3 5 6 4，这不是围绕4分区的。 - oxuser

@oxuser：是的，那就是我所说的结果。有两个片段[1,2,3,3]和[5,6,4]。在第一个片段中，所有值都小于或等于四，在第二个片段中，所有值都大于或等于四。 - Vaughn Cato

@oxuser：我已经修改了我的答案。也许现在更清晰了一些。 - Vaughn Cato

你怎么知道第二个片段从哪里开始呢？ - oxuser

@oxuser：这就是返回的内容（4）。 - Vaughn Cato

Answer 2

分区算法的目标是简单地将一些元素集合（例如，您使用“数组”）分割（或拆分！）成两个部分——左部分和右部分，围绕枢轴进行分区。

关于枢轴左侧和右侧的元素应该有一些“规则”。例如，所有左侧的元素都应该小于所选的枢轴，而所有右侧的元素都应该大于枢轴。

您还可以在以下视频中查看实现： https://www.youtube.com/watch?v=MLpH7mpwOxQ 希望这能帮到您！

- Vlad Bud