Quicksort:一个分区后的枢轴位置

Question

我正在阅读关于quicksort的内容,看看不同的实现,我正试图绕过一些东西.

在该实现中(当然可以工作),选择枢轴作为中间元素,然后左右指针相应地向右和向左移动,交换元素以围绕枢轴分区.

我正在尝试阵列[4,3,2,6,8,1,0].

在第一个分区上,pivot为6,所有左侧元素都已小于6,因此左指针将停在枢轴上.在右侧,我们将交换0与6,然后是1和8,因此在第一次迭代结束时,数组将如下所示:

[4,3,2,0,1,8,6].

然而,我的印象是,在快速排序的每次迭代之后,枢轴最终会在其合适的位置,因此它应该最终位于阵列的位置5.

因此,有可能(并且确定)枢轴不会以正确的迭代结束,或者是否是我遗漏的明显事物？

Answer 1

快速排序算法有很多可能的变体。在这一步中，枢轴在迭代中不处于正确的位置是可以的。

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

注意，一般而言，等于pivot的元素可能会到达数组的任何部分。快速排序的一个很好的实现，在最明显的情况下避免了二次时间，即所有相等的元素，必须合理地分布相等的元素以在各个部分之间进行枢轴旋转。

可能的变体包括：

• 中间部分仅包含1个元素：枢轴。在这种情况下，数据透视表在分区之后的数组中占据最后位置，并且不会在递归调用中使用。这就是透视在迭代中取代它的意思。对于这种方法，良好的实现必须将大约等于旋转一半的元素移到左边，另一半移到右边，否则对于所有元素相等的数组，我们将有二次时间。
• 没有中间部分。枢轴和所有与其相等的元素分布在左侧和右侧之间。这就是您链接的实现。再一次，在这种方法中，大约等于枢轴的元素中的一半应移至左侧，而另一半应移至右侧。也可以将其与第一个变体混合使用，具体取决于我们是对元素为奇数还是偶数的数组进行排序。
• 每个等于枢轴的元素都进入中间部分。左侧或右侧没有等于旋转的元素。那是非常有效的，这就是Wikipedia提供的解决所有元素相等问题的示例。在这种情况下，所有元素彼此相等的数组按线性时间排序。

因此，快速排序的正确和有效实现是非常棘手的（还存在一个选择良好枢纽的问题，对于这种枢纽，也存在几种具有不同权衡取舍的方法；或者针对较小的子项，切换到另一种非递归排序算法的优化-数组大小）。

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

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

例如，当i等于时j，这些元素将被交换，并i变得大于j2。之后，以下递归调用的范围之间将有3个元素重叠。该代码似乎仍然可以正常工作。