快速选择算法中的每一组都应该排序吗？

Question

我有一个问题，我的老师在他的关于快速选择算法的讲座中说，在我们把数组看作五个元素组之后，它不需要对每个组进行排序，他正确吗？因为当我们有一个像<3,5,7,6,1>这样的组而不进行排序时，我们如何才能找到中位数？谢谢

编辑:它不是关于快速选择，而是关于线性通用选择算法

Answer 1

如果您只需要中间值，那么根据排序算法的不同，首先排序可能比运行半版本的选择排序要昂贵得多。在n个元素的数组中，如果n是奇数，中位数将是中间(n/2+1)元素，如果n/2，n/2+1，则中间元素的平均值为偶数。因此，执行一个正常的选择排序，但不是运行整个O(N)操作，只运行一半才能获得所选的中值。

您也可以做非常简单的气泡排序，但只运行n/2次。这将确保中值处于中间位置，而且在概念上是容易的。如果你有疑问的话，可以在纸上手动做。

Answer 2

中间值是按排序顺序排列的floor(n / 2) + 1第四最小元素，选择算法可以在O(n)中找到这个元素(为了方便起见，认为n是奇数)。所以，如果你知道k左边的所有元素都比k小，右边的所有元素都大于k，k在floor(n / 2) + 1位置，那么就知道k是中间值。你不需要分类。

例如：

8 3 11 20 18 => 11是中间值，因为它位于中间，比它之后的所有东西都小，比它之前的所有东西都大。不需要分类。

选择算法有许多不同的变体。他们的基本想法是相同的，但有些细节可能是不同的。如果你需要更多的本地化帮助，请张贴你的老师的实施情况，并试图澄清你的问题。