algorithm - 选择算法找到中位数，元素向左和向右

Question

假设我有一个大小为 n 的未排序数组 A。

如何在线性时间内从原始未排序列表中找到第n/2、n/2−1、n/2+1个最小的元素？

我尝试使用 wikipedia 中的选择算法(基于分区的一般选择算法是我正在实现的)。

function partition(list, left, right, pivotIndex)
 pivotValue := list[pivotIndex]
 swap list[pivotIndex] and list[right]  // Move pivot to end
 storeIndex := left
 for i from left to right-1 
     if list[i] < pivotValue
         swap list[storeIndex] and list[i]
         increment storeIndex
 swap list[right] and list[storeIndex]  // Move pivot to its final place
 return storeIndex


function select(list, left, right, k)
 if left = right // If the list contains only one element
     return list[left]  // Return that element
 select pivotIndex between left and right //What value of  pivotIndex shud i select??????????
 pivotNewIndex := partition(list, left, right, pivotIndex)
 pivotDist := pivotNewIndex - left + 1 
 // The pivot is in its final sorted position, 
 // so pivotDist reflects its 1-based position if list were sorted
 if pivotDist = k 
     return list[pivotNewIndex]
 else if k < pivotDist 
     return select(list, left, pivotNewIndex - 1, k)
 else
     return select(list, pivotNewIndex + 1, right, k - pivotDist)

但是我没看懂3、4步。我有以下疑问:

1. 我是否选择了正确的算法？对于我的程序，它真的能以线性时间运行吗？我有点困惑，因为它类似于快速排序。
2. 在主函数中调用函数选择时，left、right 和 k 的值是多少。假设我的数组是列表 [1...N]。
3. 我是否必须调用 select 函数三次，一次是为了找到第 n/2 个最小值，另一次是为了找到第 n/2+1 个最小值，再调用一次是为了找到第 n/2-1 个最小值，或者可以这样做吗一次通话，如果是，怎么做？
4. 同样在函数选择(第三步)“在左右之间选择 pivotIndex”，我应该为我的程序/目的选择什么 pivotIndex 值。

谢谢!

Answer 1

它类似于快速排序，但它是线性的，因为在快速排序中，您需要同时处理枢轴的左侧和右侧，而在快速选择中，您只需处理一侧。

如果 N 是奇数，初始调用应该是 Select(A, 0, N, (N-1)/2)；如果 N 是偶数，您需要准确决定要做什么。

要找到中位数和左/右，你可能想调用它来找到中位数，然后只对左边的数组元素求最大值，对右边的元素求最小值，因为你知道一旦中值选择阶段完成，中值左侧的所有元素都将小于它，而右侧的所有元素将大于(或等于)。这是 O(n) + n/2 + n/2 = O(n) 总时间。

有很多方法可以选择枢轴索引。对于临时目的，中间元素或随机索引可能就足够了。