Quicksort：一个分区后的枢轴位置
Quicksort: pivot position after one partition
我正在阅读有关快速排序的内容，正在研究不同的实现方式，并且我正在努力思考一些事情。
在this实现中（当然可行），选择枢轴作为中间元素然后左右指针向右和向左移动因此，交换元素以围绕枢轴进行分区。
我正在尝试数组 [4, 3, 2, 6, 8, 1, 0]。
在第一个分区中，pivot为6，而所有左边的元素都已经小于6，所以left指针会停在pivot上。在右侧，我们将用 6 交换 0，然后交换 1 和 8，因此在第一次迭代结束时，数组将如下所示：
[4、3、2、0、1、8、6]。
然而，我的印象是，在快速排序中的每次迭代之后，主元都在其正确的位置结束，所以这里它应该在数组的位置 5 结束。
所以，有可能（并且没问题）枢轴没有在正确的迭代中结束，还是我明显遗漏了什么？
快速排序算法有许多可能的变体。在这一个中，枢轴在其迭代中不在正确的位置是可以的。
快速排序算法的每个变体的定义特征是在分区步骤之后，我们在数组的开头有一个部分，其中所有元素都小于或等于主元，以及一个不重叠的部分在数组的末尾，其中所有元素都大于或等于 pivot。它们之间也可能有一部分，其中每个元素都等于枢轴。这样的布局保证了，当我们递归调用对左右两部分进行排序后，保留中间部分不变，整个数组就会被排序。
注意，通常等于 pivot 的元素可能会到达数组的任何部分。快速排序的一个很好的实现，它避免了最明显情况的二次时间，即所有相等的元素，必须合理地在各部分之间传播等于枢轴的元素。
可能的变体包括：
- 中间部分仅包含 1 个元素：枢轴。在这种情况下，pivot 在分区之后在数组中占据最后位置，并且不会在递归调用中使用。这就是你所说的枢轴在其迭代中占据一席之地的意思。对于这种方法，好的实现必须将等于枢轴的大约一半元素移动到左侧部分，另一半移动到右侧部分，否则对于具有所有相等元素的数组，我们将有二次时间。
- 没有中间部分。 Pivot 和所有等于它的元素分布在左右两部分之间。这就是您链接的实现所做的。同样，在这种方法中，大约一半等于 pivot 的元素应该放在左边，另一半放在右边。这也可以与第一个变体混合使用，具体取决于我们是对元素数量为奇数还是偶数的数组进行排序。
- 每一个等于pivot的元素都到中间部分。左侧或右侧都没有等于 pivot 的元素。这非常有效，这就是 Wikipedia 给出的解决全元素相等问题的示例。在这种情况下，所有元素彼此相等的数组按线性时间排序。
因此，快速排序的正确和高效实现是相当棘手的（还有选择一个好的基准的问题，为此也存在几种具有不同权衡的方法；或者切换到另一个非递归的优化较小子数组大小的排序算法）。
此外，您链接到的实现似乎可能对重叠子数组进行递归调用：
if (i <= j) {
exchange(i, j);
i++;
j--;
}
例如，当i等于j时，这些元素将被交换，i将比j大2。之后3元素将在以下递归调用的范围之间重叠。不过代码似乎仍然可以正常工作。
我正在阅读有关快速排序的内容，正在研究不同的实现方式，并且我正在努力思考一些事情。
在this实现中（当然可行），选择枢轴作为中间元素然后左右指针向右和向左移动因此，交换元素以围绕枢轴进行分区。
我正在尝试数组 [4, 3, 2, 6, 8, 1, 0]。
在第一个分区中，pivot为6，而所有左边的元素都已经小于6，所以left指针会停在pivot上。在右侧，我们将用 6 交换 0，然后交换 1 和 8，因此在第一次迭代结束时，数组将如下所示：
[4、3、2、0、1、8、6]。
然而，我的印象是，在快速排序中的每次迭代之后，主元都在其正确的位置结束，所以这里它应该在数组的位置 5 结束。
所以，有可能（并且没问题）枢轴没有在正确的迭代中结束，还是我明显遗漏了什么？
快速排序算法有许多可能的变体。在这一个中，枢轴在其迭代中不在正确的位置是可以的。
快速排序算法的每个变体的定义特征是在分区步骤之后，我们在数组的开头有一个部分，其中所有元素都小于或等于主元，以及一个不重叠的部分在数组的末尾，其中所有元素都大于或等于 pivot。它们之间也可能有一部分，其中每个元素都等于枢轴。这样的布局保证了，当我们递归调用对左右两部分进行排序后，保留中间部分不变，整个数组就会被排序。
注意，通常等于 pivot 的元素可能会到达数组的任何部分。快速排序的一个很好的实现，它避免了最明显情况的二次时间，即所有相等的元素，必须合理地在各部分之间传播等于枢轴的元素。
可能的变体包括：
- 中间部分仅包含 1 个元素：枢轴。在这种情况下，pivot 在分区之后在数组中占据最后位置，并且不会在递归调用中使用。这就是你所说的枢轴在其迭代中占据一席之地的意思。对于这种方法，好的实现必须将等于枢轴的大约一半元素移动到左侧部分，另一半移动到右侧部分，否则对于具有所有相等元素的数组，我们将有二次时间。
- 没有中间部分。 Pivot 和所有等于它的元素分布在左右两部分之间。这就是您链接的实现所做的。同样，在这种方法中，大约一半等于 pivot 的元素应该放在左边，另一半放在右边。这也可以与第一个变体混合使用，具体取决于我们是对元素数量为奇数还是偶数的数组进行排序。
- 每一个等于pivot的元素都到中间部分。左侧或右侧都没有等于 pivot 的元素。这非常有效，这就是 Wikipedia 给出的解决全元素相等问题的示例。在这种情况下，所有元素彼此相等的数组按线性时间排序。
因此，快速排序的正确和高效实现是相当棘手的（还有选择一个好的基准的问题，为此也存在几种具有不同权衡的方法；或者切换到另一个非递归的优化较小子数组大小的排序算法）。
此外，您链接到的实现似乎可能对重叠子数组进行递归调用：
if (i <= j) {
exchange(i, j);
i++;
j--;
}
例如，当i等于j时，这些元素将被交换，i将比j大2。之后3元素将在以下递归调用的范围之间重叠。不过代码似乎仍然可以正常工作。