快速排序：一个分区后的轴心位置

Question

我正在读关于快速排序的书，看不同的实现，我正试着去想一些事情。

在这个实现中（当然可以），枢轴被选为中间元素，然后左右指针相应地向右和向左移动，将元素交换到围绕枢轴的分区中。

我正在尝试数组[4,3,2,6,8,1,0]。

在第一个分区上，pivot为6，并且所有左侧元素都已小于6，因此左指针将停止在pivot处。在右侧，我们将0与6交换，然后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个元素将在以下递归调用的范围内重叠。不过，代码似乎仍然正常工作。