介绍

Quickselect 是一种选择算法，用于寻找无序列表中第 k 个最小的元素。它与快速排序的排序算法有关。

该算法与 QuickSort 相似。不同的是，它不是对两边都进行递归（在找到支点后），而是只对包含第 k 个最小元素的部分进行递归。逻辑很简单，如果被分割的元素的索引大于 k，那么我们对左边的部分进行递归。如果索引与 k 相同，我们就找到了第 k 个最小的元素，我们就返回。如果索引小于 k，那么我们就对右边的部分进行递归。这就把预期复杂度从$O(nlogn)$ 降低到$O(n)$，最坏的情况下是$O(n^2)$。

伪代码：

function quickSelect(list, left, right, k)
 if left = right return list[left]

 Select a 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 

实现

JavaScript

// partition function similar to quick sort
// Considers last element as pivot and adds elements with less value to the left and high value to the right and also changes
// the pivot position to its respective position in the final array.
function _partition(arr, low, high) {
  let pivot = arr[high], loc = low;
  for (let i = low; i <= high; i++) {
    // inserting elements of less value to the left of the pivot location
    if (arr[i] < pivot) {
      [arr[i], arr[loc]] = [arr[loc], arr[i]];
      loc++;
    }
  }
  // swapping pivot to the final pivot location
  [arr[high], arr[loc]] = [arr[loc], arr[high]];
  return loc;
}
  
// finds the kth position (of the sorted array) in a given unsorted array i.e this function can be used to find both kth largest and kth smallest element in the array.
// ASSUMPTION: all elements in arr[] are distinct
function kthSmallest(arr, low, high, k) {
  // find the partition
  let partition = _partition(arr, low, high);

  // if partition value is equal to the kth position, return value at k.
  if (partition == k - 1) return arr[partition];
  // if partition value is less than kth position, search right side of the array.
  else if (partition < k - 1) return kthSmallest(arr, partition + 1, high, k);
  // if partition value is more than kth position, search left side of the array.
  return kthSmallest(arr, low, partition - 1, k);
}

或者：

/**
 * [QuickSelect](https://www.geeksforgeeks.org/quickselect-algorithm/) is an algorithm to find the kth smallest number
 *
 * Notes:
 * -QuickSelect is related to QuickSort, thus has optimal best and average
 * -case (O(n)) but unlikely poor worst case (O(n^2))
 * -This implementation uses randomly selected pivots for better performance
 *
 * @complexity: O(n) (on average )
 * @complexity: O(n^2) (worst case)
 * @flow
 */

function QuickSelect (items, kth) { // eslint-disable-line no-unused-vars
  if (kth < 1 || kth > items.length) {
    throw new RangeError('Index Out of Bound')
  }

  return RandomizedSelect(items, 0, items.length - 1, kth)
}

function RandomizedSelect (items, left, right, i) {
  if (left === right) return items[left]

  const pivotIndex = RandomizedPartition(items, left, right)
  const k = pivotIndex - left + 1

  if (i === k) return items[pivotIndex]
  if (i < k) return RandomizedSelect(items, left, pivotIndex - 1, i)

  return RandomizedSelect(items, pivotIndex + 1, right, i - k)
}

function RandomizedPartition (items, left, right) {
  const rand = getRandomInt(left, right)
  Swap(items, rand, right)
  return Partition(items, left, right)
}

function Partition (items, left, right) {
  const x = items[right]
  let pivotIndex = left - 1

  for (let j = left; j < right; j++) {
    if (items[j] <= x) {
      pivotIndex++
      Swap(items, pivotIndex, j)
    }
  }

  Swap(items, pivotIndex + 1, right)

  return pivotIndex + 1
}

function getRandomInt (min, max) {
  return Math.floor(Math.random() * (max - min + 1)) + min
}

function Swap (arr, x, y) {
  [arr[x], arr[y]] = [arr[y], arr[x]]
}

参考

• Quickselect Algorithm - GeeksforGeeks (opens new window)