quickselect - 尝试手动使用快速选择

Question

我有一个子数组 {8,9,7}。假设选择的枢轴是 8。在这个数组上运行 Quickselect 给了我一些问题。所以左指针从左边开始寻找大于 8 的元素找到 9。右指针从右边开始寻找小于 8 的元素找到 7。7 和 9 交换位置。{8,7,9} 现在左指针再次找到 9，右指针找到 7。但是现在它们已经相互交叉，所以我们不执行交换。相反，左指针与创建数组 {9,7,8} 的枢轴交换，但这并不好，因为较小的元素现在不在枢轴的左侧。那么我做错了什么？

Answer 1

这是很久以后的事了，所以你无疑已经想通了，但是为了后代：

上面描述的第一部分与 QuickSelect（或 QuickSort）中的第一个分区步骤匹配，使用零索引（此处为值 8）作为枢轴。

{8,7,9}变化是正确的 - 两部分并{8,7}满足{9}枢轴值的划分标准8。然后递归处理这些以完成排序，如果排序的话。当然，如果您（快速）选择，您只处理您寻找的索引所在的部分。

该left pointer is swapped with the pivot步骤不适用于此处。仅当您使用将枢轴移动到前面或后面的变体时才应该这样做，如果它不存在，然后从分区过程中排除枢轴索引。只有当你这样做时，才需要将枢轴值移动到两个分区相交的位置。