9

我一直在看《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 是枢轴值。左 = 0，右 = 6

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

    1 2 3 3 5 6 4

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

但是，我最终得到的数组：

1 2 3 3 5 6 4

没有围绕 4 进行分区。我是否错误地执行了步骤或算法不正确？我已经仔细检查了我对算法的复制，并且我已经正确地复制了它。

另外，我不确定为什么分区会向左返回，它是否会返回枢轴？

我了解分区和快速排序的 Wikipedia 实现，但我试图了解这里发生的事情。

4

2 回答 2

6

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

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

于 2012-07-23T03:49:12.073 回答
0

分区算法的目标是简单地获取一些元素的集合（例如，您使用“数组”），然后围绕枢轴将该集合分区（或拆分！）为两部分 - 左侧部分和右侧部分。

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

您还可以在以下视频中看到实施： https ://www.youtube.com/watch?v=MLpH7mpwOxQ

希望有帮助！

于 2019-10-26T13:26:29.450 回答