尝试手动使用快速选择
我有一个子数组是{8,9,7}。假设选取的枢轴是8。在此数组上运行Quickselect会给我带来一些问题。所以左指针从左开始查找大于8的元素，右指针从右开始查找小于8的元素，它找到7.7和9的交换位置。{8, 7 ,9}现在左指针又找到了9，右指针又找到了7，但现在它们彼此交叉了，所以我们不执行交换。相反，左指针与创建数组{9,7,8}的轴心互换，但这并不好，因为较小的元素现在不在轴心的左边。那么我做错了什么呢？
回答 1
Stack Overflow用户
发布于 2019-09-27 19:36:51
这是很久以后的事了，所以你肯定已经弄明白了，但对于后人来说：
上面描述的第一部分匹配QuickSelect (或QuickSort)中的第一个分区步骤，使用零索引(这里的值为8)作为轴心。
{8,7,9}的变化是正确的-两个部分{8,7}和{9}满足8轴值的划分标准。如果排序，则递归地处理这些数据以完成排序。当然，如果您正在(快速)选择，则只处理所查找的索引所在的部分。
left pointer is swapped with the pivot步骤不适用于此。只有在您将轴心移到前面或后面，然后从分区过程中排除了轴心索引的情况下，才应该这样做。只有这样，才需要将轴值移动到两个分区相交的位置。
https://stackoverflow.com/questions/56354200
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号