# 快速选择

（重定向自Quickselect

分类 快速选择算法的动画演示：选择第22小的元素。（注意：这和条目中的算法不完全相同） 选择算法 数组 О(n2) О(n) O(n) O(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


  // Returns the k-th smallest element of list within left..right inclusive
// (i.e. left <= k <= right).
// The search space within the array is changing for each round - but the list
// is still the same size. Thus, k does not need to be updated with each round.
function select(list, left, right, k)
if left = right        // If the list contains only one element,
return list[left]  // return that element
pivotIndex  := ...     // select a pivotIndex between left and right,
// e.g., left + floor(rand() % (right - left + 1))
pivotIndex  := partition(list, left, right, pivotIndex)
// The pivot is in its final sorted position
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)


 function select(list, left, right, k)
loop
if left = right
return list[left]
pivotIndex := ...     // select pivotIndex between left and right
pivotIndex := partition(list, left, right, pivotIndex)
if k = pivotIndex
return list[k]
else if k < pivotIndex
right := pivotIndex - 1
else
left := pivotIndex + 1