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

如何在线性时间内从原始未排序列表中找到N/2，N/21，N/2+1个最小元素？

我尝试使用维基百科中的选择算法（基于分区的通用选择算法就是我正在实现的）。

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. 在函数选择（第三步）“select pivotIndex between left and right”中，我应该为我的程序/目的选择什么pivotIndex值。/li>

谢啦！