问题标签 [quickselect]

我已经实现了以下快速选择算法来实现O(n)中位数选择的复杂性（更一般地说是第 k 个最小的数字）：

然后我尝试将它与 glibc 进行比较，qsort()并O(nlog(n))对其卓越的性能感到惊讶。这是测量代码：

对于 10000 个元素的数组，qsort took 0.280432结果类似于。qselect took 8.516676为什么快速排序比快速选择快？

是否有一个现成的等效numpy.partition于 JavaScript，通过库或内置？

似乎没有任何流行的相关库（例如underscore.js ）提供这样的功能。我之所以问，是因为我希望能够n在一般情况下找到数组中最高（或最低）的元素，而不必自己实现快速选择或内推。

在 index 处对数组进行分区会n重新排列数组，以便 at 的元素n按排序顺序排列，并且索引大于 的所有元素n都大于 at 的元素n。或者，索引小于的元素n都可以小于 的元素n。无论哪种方式，它都是一种部分排序，可以保证特定元素的位置以及它上面和下面的元素的分布。

完全排序当然满足相同的条件，但会O(n log n)及时运行，而分区通常会O(n)及时运行（快速选择的平均情况，introselect 的最坏情况）。

jQuery 插件QuickSelect做了一些完全不同的事情，尽管这个名字很有希望。

这个问题的部分动机：可能使用 Math.min 从数组中获取第二小的数字？

在这张快速选择的演讲幻灯片中，“ k ”到底是什么意思？

我正在尝试编写最佳算法来选择列表中较大的第 i 个元素。例如，如果 array = [4,3,5,7] 并且我搜索第二个，该函数将返回 4。

我假设列表在这里只有不同的数字

这是问题所在：

该函数有时会返回 None。

这是我的代码（我认为第一个函数运行良好）。

我已尝试实现本文所述的 C QuickSelect 算法（3 路快速排序（C 实现））。但是，我得到的只是性能比默认的 qsort 低 5 到 10 倍（即使是初始改组）。我试图挖掘此处提供的原始 qsort 源代码（https://github.com/lattera/glibc/blob/master/stdlib/qsort.c），但它太复杂了。有人有更简单，更好的算法吗？欢迎任何想法。谢谢，注意：我最初的问题是尝试将数组的第 K 个最小值获取到第一个 Kth 索引。所以我计划调用 quickselect K 次编辑 1：这是从上面的链接复制和改编的 Cython 代码

我使用 python timeit 来获得方法 pyselect（N=50）和 pysort 的性能。像这样

QuickSelect 算法是否适用于重复值？

如果我有一个数组

即使有重复，它是否能够获得第 k 个最小的元素？

我正在尝试了解 QuickSelect 分区是如何工作的，并且有一些我没有得到的东西，我将尝试解释我是如何看待它的（请注意，我已重命名变量并发表评论以试图理解它，所以也许一些重命名或评论是错误的）：

• 首先，枢轴的值是枢轴所在索引的值，这是有道理的。
• 我们现在将枢轴交换到数组的末尾，为什么？
• 我们有一个从左边开始的第一个指针，因为第一个指针当然应该从开头开始。
• 在 for 循环中我们有第二个指针，它也从左边开始，为什么？. 不应该从另一端开始吗？
• 如果我们所在的位置小于枢轴值，则交换它们，因此我们将较小的元素放在左侧。
• 最后交换枢轴（这导致我的拳头“为什么”）。
• 最后我们返回第一个指针，我认为这是因为这是数组中唯一剩下的元素？

我见过不同类型的实现，我发现大多数（如果不是全部）都这样做。

我做了快速选择算法，就是在一个数组中找到第k个最小的数。我的问题是，它只适用于没有重复的数组。如果我有一个数组

arr = {1,2,2,3,5,5,8,2,4,8,8}

它会说第三小的数字是 2，但实际上是 3。

我被困在做什么，这是我的两个方法 quickSelect 和 Partition：

我正在学习快速选择以找到第 K 个最小的数字。我理解了这个程序。但我对 QuickSelect 的平均时间复杂度是 O(n) 感到困惑。

我已经尝试了 Java 中的代码并且它有效。但我被时间复杂性困住了。

平均时间复杂度 O(n) 是多少？任何人都可以向我详细解释一下吗？

我正在使用此 Rcpp 代码对值向量进行快速选择，即在 O(n) 时间内从向量中获取第 k 个最大元素（我将其保存为qselect.cpp）：

我将其用作计算所需百分位数的快速方法。例如

[这可能看起来已经很快，但我需要在我的应用程序中执行数百万次]

现在我想修改这个 Rcpp 函数，以便它对 R 矩阵的所有列或所有行执行多线程快速选择，并将结果作为向量返回。由于我是 Rcpp 的新手，我想要一些建议，但关于哪个框架可能是最快的并且最容易编码（它必须很容易跨平台工作，我需要对 nr 进行良好的控制要使用的线程数）。使用OpenMP、RcppParallel还是RcppThread？甚至更好 - 如果有人可以展示一种快速而优雅的方式来做到这一点？