问题标签 [quickselect]

我正在尝试实现 Quickselect，它应该在整数数组中找到第 k 个最小的元素。但是，函数 findKthSmallest() 返回第 k 个值，而不是第 k 个最小值。我不知道为什么会发生这种情况——我尝试了很多小改动，现在已经重构和重写了几次。看起来应该很简单，但我不知道。这是我的 C++ 代码：

这是它的输出：

第 4 个最小的元素（从第 0 个开始）应该是 6，而不是 12。你们知道出了什么问题吗？

使用三中位数的中位数分区策略的快速选择的渐近运行时间是多少？我觉得它应该与普通的快速选择和快速排序相同，除了最坏的情况得到缓解的事实。我是对的还是还有更多？

我正在尝试使用快速选择来查找第 k 个最小的数字。但是当我编写与https://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array/完全相同的代码时，它会给出错误的输出，但是当我从 GeeksforGeeks 复制代码时它可以工作。我使用相同的头文件，但它不起作用。

我的代码是

我正在尝试完成一个程序来执行快速选择算法并使用向量，因为元素是随机生成的。当我现在运行我的代码时，我得到了错误：

当我从向量声明和引用中删除所有“&”和“*”符号，并尝试在我的 quickSelect 函数中打印向量的值时，我得到一堆不准确的随机值。当我在主函数中打印向量的值时，我得到了正确的值。这让我相信当我将向量传递给函数时发生了一些事情。如何将正确的值传递给函数 quickSelect？

假设 A = [1, 2, 3, 4, 5, 6, 7, 8, 9]。我必须在这里找到中位数，即 5，并且我需要使用快速选择和中位数的概念。我制作了以下代码，但由于某种原因，它输出 4 这是错误的。我哪里错了？

以下只是后面功能需要的一些辅助功能。

对于以下内容，我编写了中位数的代码。这样做是将整个数组划分为 5 个元素的组，最多 1 个包含少于 5 个元素的组。

现在这是它使用中位数中位数中的中位数对数组进行分区的部分

这是 quick_select 的功能

这是 main() 的函数

我正在实施快速选择算法以获取k数组中的第 th 个元素，但我被困在一个我不知道如何解决的地方。这是我的代码不起作用：

当然，如果我删除这些行：

它变成快速排序并且工作正常。而且我理解为什么它不起作用，这是因为我从 0 到 k 的数组在我以上述条件返回时可能不会被排序。但是我无法找到正确的条件，我只对数组中的前 k 个元素进行排序而忽略其余的，所以我不做任何额外的工作。我在网上查看了一些实现并在上面花了一些时间，但无法弄清楚，所以寻求帮助。

我是 Python 新手，我正在练习编写代码，但我遇到了一些麻烦。

我正在尝试实现一种基于QuickSelect的算法，在该算法中可以提取K 个最大元素。

所以，在我实现QuickSelect算法并使用它找到数组 A 中的第 K 个最大元素之前。然​​后使用函数k_largest_quickselect(A, K)我扫描数组 A 以收集大于或等于找到的第 K 个元素的 K 个元素，最后QuickSelect，对收集到的元素进行排序。

这是我的实现代码：

我试图测试算法

得到这个结果

如您所见，通过使用该函数，k_largest_quickselect(A = a, K = 3)我没有得到数组的 3 个最大元素。

拜托，你能帮我解决这个问题吗？非常感谢！

我是 Python 新手，我正在练习编写代码，但我遇到了一些麻烦。

我正在尝试实现QuickSelect以提取K 最大元素。

这是我的代码；

尝试实现算法以获得第 5 个最高元素：

得到这个结果：

结果是错误的，因为 3 不是第 5 个最高元素。

错误是在partition(A, left, right)还是在QuickSelect(A, K, left, right)？你能帮我解决它吗？谢谢！

我不确定 Quickselect 算法的时间复杂度（对于第 k 个最大元素），所以任何人都可以帮助我

这是我的代码，我使用了快速选择算法。在这个问题中，我的目标是获得第 k 个最大的元素。尽管我试图涵盖所有内容并且通过了许多测试用例，但它在某些测试用例上给出了错误的答案。我尝试使用 cout 语句来获取错误，但根据我的试运行，我应该得到正确的输出。但是，当我尝试在第一个分区之后打印元素时，虽然 4 应该最终根据交换移动到索引 3 和 5，但那没有发生，4 仍然在最后，5 在索引 3。我无法弄清楚。请帮我解决这个问题。如果需要任何进一步的澄清，我会尽力以最好的方式解释这个问题，我很乐意提供。谢谢你。