快速选择算法借鉴快速排序算法,快速排序的算法如下:
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
上述算法是在数组中将pivotIndex位置处的值插入到left到right之间的适当位置,使storeIndex之前的值都比他小,之后的值都比他大。
function select(list, left, right, k)
if left = right
return list[left]
pivotIndex := ... //随机一个数
pivotIndex := partition(list, left, right, pivotIndex
if k = pivotIndex
return list[k]
else if k < pivotIndex
return select(list, left, pivotIndex - 1, k)
else
return select(list, pivotIndex + 1, right, k)