问题标签 [quickselect]

我尝试使用“随机枢轴”方法在给定数组中找到第 K 个最小元素。
[编码]

但结果是不稳定的，有时对有时错。
请看一下findKthMin_RanP_Helper方法的第 5 行：
如果我把它改成int split = partition(givenArray, start, end, rand);，int split = partition(givenArray, start, end, end);结果总是正确的。
我真的找不到这有什么问题。

---

编辑：
问题来自“分区”，新分区应该是这样的：

并且findKthMin_RanP_Helper应该像这样更改：

终于找到bug了，请看第二个EDIT
但是还有那个问题，你看，“getMedian()”方法的最后第四行，我对medians[]数组进行排序，求出中位数的中位数。我个人认为这打破了最坏情况的时间复杂度 = O(n)，对吗？

---

我尝试使用中位数的中位数作为枢轴来划分数组以找到第 K 个最大元素。

但是这个 bug 很奇怪：例如 {8, 5, 2, 0, 9, 1}，输出是：

• k = 1，输出 >> 9。
• k = 2，输出 >> 9。
• k = 3，输出 >> 5。
• k = 4，输出 >> 2。
• k = 5，输出 >> 1。
• k = 6，输出 >> 0。
• 第二个最大元素的输出是错误的，其他的很好。

另一个问题：

在getMedian (int[] givenArray, int start, int end)方法的最后第二行，我对中位数数组进行排序，我认为这个操作打破了 O(n) 的时间复杂度，对吗？

---

编辑
我个人认为，该错误可能存在于两个地方：

• 在“ partition (int[] givenArray, int start, int end, int pivot)”
• >

[代码]

• 在“ findKthMax_MOM_Helper (int[] givenArray, int start, int end, int k)”
• >

[代码]

---

第二次编辑
最后我发现了这个错误，我的代码的错误部分是在“getMedian()”方法处，看看那个方法的最后三句话。
[代码]

我正在尝试实现快速选择算法。不过，我已经很好地理解了它背后的理论；我发现很难将其转换为运行良好的程序。

以下是我将如何逐步实施它以及我面临问题的地方：

问题：在 A[] = {2,1,3,7,5,4,6} 中找到第四小的元素

k = 4.

指数：0|1|2|3|4|5|6

对应值：2|1|3|7|5|4|6

最初，l = 0并且r = 6

第 1 步）将枢轴作为最左边的元素（在这个问题中，枢轴总是最左边的）-

pivot_index = 0

pivot_value = 2

步骤 2)应用分区算法；将枢轴放在正确的位置（[<p][p][>p]）-

我们得到以下数组：1|2|3|7|5|4|6

在哪里，pivot_index = i-1 = 1

因此，pivot_value = 2

步骤 3 )比较pivot_index-k

k=3, pivot_index = 1; k>pivot_index

因此，我们的第 k 个最小数字位于数组的右侧。

右数组 =i to r并且我们不再为左部分 ( l to i-1) 操心了。

Step 4)我们修改kas k - (pivot_index)=> 4-1 = 2 的值；k = 3.

问题是：不应该k是 2 吗？因为我们在数组的左边有两个值：1|2？我们应该计算k为k - (pivot_index+1)吗？

让我们假设k = 3是正确的。

步骤 5）要处理的“新”数组：3|7|5|4|6具有相应的索引：2|3|4|5|6

现在，pivot_index = 2和pivot_index = 3

步骤 6)在上述数组上应用分区算法-

3|7|5|4|6（数组保持不变，因为枢轴本身是最小值）。 i = 3

pivot_index = i-1 = 2 pivot_value = 3

步骤 7pivot_index )比较k

k=3和pivot_index=2

k > pivot_index

等等....

这种方法正确吗？

这是我的代码不起作用。我使用随机数生成器来选择一个随机枢轴，然后将枢轴与数组中的第一个元素交换。

我正在寻找一种有效的算法来执行以下操作：给定一个包含 N 个项目的数组，以某种方式对其进行排序，以便项目作为 M 个相等的组，其中每个组未排序，但组在彼此之间排序（所有元素一组中的元素小于下一组的任何元素）。

最简单的方法是对整个数组进行排序。但它的效率很低，特别是如果组的数量远小于项目的总数（例如将一百万个项目分成 5 个组）。

目前我已经决定使用快速选择算法（具体来说，它是Floyd-Rivest 变体）将一个数组排序为 2 个未排序的组，然后应用它 M-1 次。一个显着的改进可能是对快速选择应用分而治之的方法，首先将数组分为两组，然后对每一半进行排序，等等，直到我们有 M 个组。一种对无序部分排序问题的概括。

但我有一种直觉，可能有一种更简单、更有效的方法来解决这个问题。有什么我想念的吗？有任何想法吗？我需要它来提高我的RBush JavaScript 库（一种高效的 R*-tree 实现）中的批量插入性能。

I have to implement an algorithm that returns the median of an array. So I chose to implement Quickselect which seems to be efficient for this and I saw that for the tripartition I can use the same partition algorithm used in Quicksort.

The partition algorithm reported in my lecture notes (in C code) is the following:

Now, if my array is: a = [40, 20, 100, 60, 80] and I choose as pivot the number 80, the result is: a = [40, 20, 80, 60, 100], but as you can see the values in the right partition are not all > 80 (we have 60). If I choose any other number the algorithm works properly.

Is this algorithm wrong?

Thank you for your help in advance!

中位数快速排序的最坏情况时间复杂度是多少（枢轴由需要 O(n) 时间才能找到的中位数的中位数确定）？

我正在尝试参考以下链接 http://www.cs.yale.edu/homes/aspnes/pinewiki/QuickSelect.html中给出的算法来实现快速选择

但是程序会因许多 k 值而崩溃，并且仅在少数情况下可以正常工作。请指导我哪里做错了。

我试图在具有随机生成数字的数组上实现快速选择算法。现在在代码中编写算法之后，它不会将数组从最低到最高排序，我也无法找到第 k 个最小的元素。我会很感激我得到的帮助。谢谢你。

在最后一个元素上选择随机枢轴以进行快速选择有什么意义吗？

我仍然可以通过始终选择最后一个元素作为枢轴来找到所需的元素。它会影响运行时。

我知道线性选择（中位数算法的中位数）递归方程如下：

但是这些术语是从哪里来的呢？我一直在努力理解，但我非常困惑。任何人都可以阐明一下吗？