问题标签 [quickselect]

我一直在研究各种讨论快速排序和快速选择的教程和文章，但是我对它们的理解仍然不稳定。

鉴于这种代码结构，我需要能够掌握并解释 quickselect 的工作原理。

在分解成伪代码方面我需要一点帮助，虽然我没有获得分区函数代码，但我想了解它会在提供的快速选择函数的情况下做什么。

我知道快速排序是如何工作的，只是不知道快速选择。我刚刚提供的代码是我们获得的关于如何格式化快速选择的示例。

编辑：更正的代码是

礼貌：@海涛

是否可以在多集（值可以重复）上在 O(n) 中执行搜索第 k 个元素？

因为据我了解快速选择的想法，我必须使用一些枢轴对输入进行分区。然后我有 2 个数组，我选择用于递归搜索取决于我正在搜索的索引元素 + 两个数组的大小，例如：

1 7 8 5 3 2 4

假设枢轴是 4 我正在搜索第二大元素。所以分区后我可能会得到类似的订单

1 3 2 4 7 8 5

因为右子数组由 3 个元素组成，如果我是正确的，我仍然会尝试在右数组中找到第二大元素？

但是，如果我以 8 作为支点，我可能会得到类似的东西

1 3 2 7 5 4 8

因此我会尝试在左表中找到最大的元素（可能是线性的，但通常我会采用左子数组并搜索元素 - (|右子数组大小| + 1)）

但是多集呢？假设我有数组：

4 5 6 7 7 7 4 3 2 1

我的支点是 6 搜索第三大元素，分区后我收到：

4 5 3 2 4 1 6 7 7 7

所以如果我使用上面介绍的方法，我将尝试在右子数组上执行递归，而很明显第三个最大值是左边的 5？

我想出的唯一解决方案是使用一些数据结构（如 BST、Set 等）来 O(nlogn) 过滤掉重复项。然后使用 O(n) 快速选择。但是总的来说，它会给我非线性方法，这可以线性完成吗？

我还有一个额外的问题，如果无法分配内存怎么办？我能做的就是只使用本地整数+堆栈递归。这个问题可以在 O(n) 中解决吗？因为 O(nlogn) 可以通过排序 + 线性“通过计数”来完成。

我有实现这里讨论的快速选择的小型 python 代码。

我似乎遇到了一个随机错误。有什么事吗？

编辑：实施random.choice而不是random.randint. 上面的代码似乎工作正常。感谢用户搅拌机。

如果你不介意，我有一点功课帮助。基本上这个想法是对一组值执行快速选择，但是我们得到了一个模板，我似乎无法弄清楚如何让这些函数与所提供的内容一起工作。

问题是这些值不会正确排列，或者如果它们排列正确，它们会在每次输入相同的值时发生变化。

这是我正在使用的函数，我将在代码之后用 /**/ 表示我编写的代码，任何其他行都是为我提供的模板的一部分。

我的“test.txt”文件包含以下值：

对此的任何帮助将不胜感激。我的教授根本没有解释这将如何工作，我在网上找到的任何其他示例都不能回答我的问题。我花了很多时间摆弄不同的实现方式，此时我只是不知道。谢谢

编辑：更改，现在可以直接实现和编译。还添加了我正在使用的库

我正在尝试在 C++ 中使用 quickselect 来执行此操作，但它不断返回我第 k 个最小的元素而不是第 k 个最大的元素。我的逻辑哪里错了？

我应该改变什么来使这个第 k 个最大而不是第 k 个最小的元素？

所以我试图在 C++ 中实现一个快速选择算法，以便在向量中找到中值，但是它没有正确地对列表进行部分排序，也没有返回正确的中值。

我似乎找不到错误在哪里。我是这个算法的新手，这是我第一次尝试实现它。我在下面包含了我的代码，所以如果比我更博学的人对出了什么问题有任何想法，我将非常感谢您的意见。

这是快速选择的代码

我遇到的问题是它运行时没有错误或任何东西，但是当它自己完成时，我希望它向 python shell 输出一些东西（在这种特定情况下是列表的中位数），但我什么也没得到. 我在这里做错了吗？

至于我为 lst 和 k 输入的内容......

• lst = [70, 120, 170, 200]
• k = len(lst) // 2

我也尝试了一些不同的 k 值，但无济于事

好的，所以我开发了一个通用的快速选择函数，它用于查找列表的中位数。

那么，如果枢轴每次都从列表的第一项开始，程序的行为会有什么不同。我必须把它放在中心吗？另外，我应该从哪里开始 time.clock() 以查找函数的经过时间。这是代码

在做一些事情时，我遇到了一个奇怪的问题，我无法弄清楚。我以两种方式对包含 10,000 个值的列表进行排序，一种使用快速选择，另一种使用插入排序。这样做的目标是找到一个中值，然后使用所述中值我必须找到中值和所有值之间的总距离。中位数计算工作得非常好，但由于我无法理解的原因，总计算返回不同的值。计算总数的函数的输入是列表和中位数。两个程序之间的中位数保持不变，列表的值也一样，但是其中一个列表已排序，而另一个列表未排序。

这是我用来计算总数的内容（对此的格式很好，它只是复制到这里很奇怪）......

一个列表被排序而另一个列表没有被排序，为什么我会得到截然不同的值？作为参考，我在使用插入排序时得到的距离是 49846.0，但在使用快速选择时得到的距离是 29982

So I have developed the code for a quick select function but it doesn't seem to be printing out the median. I have the main function prompt for a file name and then import that txt file, split it up into a list of numerals this is the txt file:

It gets imported into a list:

when it runs through the quickselect function it prints out the elapsed time being an odd number that changes every time something like 1.9083486328125e-06... first off what value of time is this in milliseconds? and when the function runs and returns the pivot it spits out this:

Can someone tell me why it isn't working? this is the code: