这个分区算法是否正确？

我一直在看“破解编码面试”（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

这是分区如何为我逐步解决的

4是支点值。 左= 0，右= 6

左= 3，右= 6。交换。

1 2 3 3 5 6 4

左= 4，右= 4。退出

然而，阵列我结束了：

1 2 3 3 5 6 4

没有分区4.我是否错误地执行了步骤，或者算法不正确？ 我再次检查了算法的复制，并且我已经正确复制了它。

此外，我不是积极的为什么分区返回左边，它是否返回枢轴？

我了解维基百科对分区和快速排序的实现，但我正在试图围绕这里发生的事情进行讨论。

---

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

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

链接地址: http://www.djcxy.com/p/61819.html

上一篇: Is this partition algorithm correct?

下一篇: Getting all groups an user is a member of through oauth (google)