选择算法来查找中位数，左侧和右侧的元素

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次最小，还是可以做到如果是，如何？
4. 同样在函数中选择（第三步）“选择左右之间的pivotIndex”，我应该为我的程序/目的选择什么值的pivotIndex。

谢谢！

Answer 1

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

如果N是奇数，则初始调用应为Select(A, 0, N, (N-1)/2);如果N是偶数，你需要确定你想要做什么。

要找到中位数和左/右，您可能需要调用它来查找中位数，然后仅将数组的最大值设置为左侧，将最小值设置为右侧，因为你知道一旦中值选择阶段完成，中位数左边的所有元素都将小于它，而右边的元素将会更大（或相等）。这是O（n）+ n/2 + n/2 = O（n）的总时间。

有很多方法可以选择枢纽指数。对于偶然的目的，中间元素或随机索引可能就足够了。