快速排序:在一个分区之后的枢轴位置

Question

我正在阅读快速排序，看不同的实现，我试图把我的头脑围绕着什么东西。

在这实现(当然是有效的)中，选择枢轴作为中间元素，然后左右指针相应地向右和向左移动，交换元素以围绕支点进行分区。

我正在尝试数组4，3，2，6，8，1，0。

在第一个分区上，枢轴为6，所有左元素都小于6，因此左指针将停止在枢轴处。在右侧，我们将用6交换0，然后交换1和8，因此在第一次迭代结束时，数组如下所示：

4，3，2，0，1，8，6。

然而，我的印象是，在快速排序中的每一次迭代之后，支点都会在其正确的位置结束，因此在这里它应该在数组的第5位置结束。

因此，有可能(也可以)枢轴没有在其正确的迭代中结束，或者它是否是明显的我缺少的东西？

Answer 1

快速排序算法有许多可能的变化。在这个例子中，枢轴在迭代中的位置不正确是可以的。

快速排序算法的每个变化的定义特征是，在分区步骤之后，我们在数组的开头有一个部分，其中所有元素都小于或等于枢轴，在数组末尾有一个不重叠的部分，其中所有元素都大于或等于枢轴。它们之间也可能有一部分，其中每个元素都等于枢轴。这个布局确保，在我们用递归调用对左部分和右部分进行排序之后，并保持中间部分的完整，整个数组将被排序。

注意，在一般情况下，等于枢轴的元素可以转到数组的任何部分。一个好的快速排序的实现，避免了最明显的情况下的二次型时间，即所有相等的元素，都必须合理地在各部分之间展开等于枢轴的元素。

可能的备选案文包括：

• 中间部分只包含一个元素:枢轴。在这种情况下，pivot将在分区之后的数组中占据其最后位置，并且不会在递归调用中使用。这就是你所说的支点在迭代中的位置。对于这种方法，良好的实现必须将大约一半等于枢轴的元素移动到左侧，另一半移动到右侧，否则，对于所有相同元素的数组，我们将有二次时间。
• 没有中间部分。枢轴和与其相等的所有元素都分布在左侧和右侧之间。这就是您所链接的实现所做的。同样，在这种方法中，大约一半等于枢轴的元素应该转到左边，另一半应该转到右边。这也可以与第一个变体相混合，这取决于我们是用奇数还是偶数对数组进行排序。
• 每一个等于枢轴的元素都位于中间部分。没有任何元素等于枢轴在左或右的部分。这是非常有效的，这就是维基百科给出的解决所有元素平等问题的例子。在这种情况下，具有所有元素相等的数组按线性时间排序。

因此，快速排序的正确和有效的实现是相当棘手的(还存在选择一个好的支点的问题，对于这个问题也存在着几种具有不同权衡的方法；或者优化切换到另一种更小的子数组大小的非递归排序算法)。

此外，您链接到的实现似乎可以对重叠子数组执行递归调用：

if (i <= j) {
  exchange(i, j);
  i++;
  j--;
}

例如，当i等于j时，这些元素将被交换，i将比j大2。在此之后，3个元素将在以下递归调用的范围内重叠。不过，这段代码似乎仍然正常工作。