quickselect_QuickSelect：使用代码示例解释的快速选择算法

quickselect

什么是QuickSelect？ (What is QuickSelect?)

QuickSelect is a selection algorithm to find the K-th smallest element in an unsorted list.

QuickSelect是一种选择算法，用于在未排序的列表中查找第K个最小的元素。

算法说明 (The Algorithm Explained)

After finding the pivot (a position that partitions the list into two parts: every element on the left is less than the pivot and every element on the right is more than the pivot) the algorithm recurs only for the part that contains the k-th smallest element.

找到枢轴后(将列表分为两部分的位置：左侧的每个元素均小于枢轴，右侧的每个元素均大于枢轴)，该算法仅针对包含第k个部分的部分重复最小的元素。

If the index of the partitioned element (pivot) is more than k, then the algorithm recurs for the left part. If the index (pivot) is same as k, then we have found the k-th smallest element and it is returned. If index is less than k, then the algorithm recurs for the right part.

如果分区元素的索引(枢轴)大于k，则该算法从左侧开始重复。 如果索引(枢轴)与k相同，则我们找到了第k个最小元素，并将其返回。 如果index小于k，则算法在右部分重复执行。

选择伪码 (Selection Psudocode)

Input : List, left is first position of list, right is last position of list and k is k-th smallest element.
Output : A new list is partitioned.

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

划分 (Partition)

Partition is to find the pivot as mentioned above. (Every element on the left is less than the pivot and every element on the right is more than pivot) There are two algorithm for finding the pivot of partition.

分区是为了找到如上所述的枢轴。 (左边的每个元素都小于轴，右边的每个元素都大于轴)有两种算法可以找到分区的轴。

• Lomuto Partition
  Lomuto分区
• Hoare Partition
  霍尔分区

Lomuto分区 (Lomuto Partition)

This partition chooses a pivot that is typically the last element in the array. The algorithm maintains index i as it scans the array using another index j such that the elements lo through i (inclusive) are less than or equal to the pivot, and the elements i+1 through j-1 (inclusive) are greater than the pivot.

该分区选择一个枢轴，该枢轴通常是数组中的最后一个元素。 该算法在使用另一个索引j扫描数组时会维护索引i，以使元素lo至i(包括)小于或等于枢轴，元素i + 1至j-1(包括)大于元素。枢。

This scheme degrades to O(n^2) when the array is already in order.

当阵列已经排列好时，此方案降级为O(n^2) 。

algorithm Lomuto(A, lo, hi) is
    pivot := A[hi]
    i := lo    
    for j := lo to hi - 1 do
        if A[j] < pivot then
            if i != j then
                swap A[i] with A[j]
            i := i + 1
    swap A[i] with A[hi]
    return i

霍尔分区 (Hoare Partition)

Hoare uses two indices that start at the ends of the array being partitioned, then move toward each other until they detect an inversion: a pair of elements, one greater than or equal to the pivot, one less than or equal to the pivot, that are in the wrong order relative to each other.

Hoare使用两个索引，它们从被分割的数组的末端开始，然后彼此靠近，直到它们检测到反转：一对元素，一个大于或等于枢轴，一个小于或等于枢轴，彼此的顺序错误。

The inverted elements are then swapped. When the indices meet, the algorithm stops and returns the final index. There are many variants of this algorithm.

然后交换倒置的元素。 当索引满足时，算法停止并返回最终索引。 此算法有很多变体。

algorithm Hoare(A, lo, hi) is
    pivot := A[lo]
    i := lo - 1
    j := hi + 1
    loop forever
        do
            i := i + 1
        while A[i] < pivot

        do
            j := j - 1
        while A[j] > pivot

        if i >= j then
            return j

        swap A[i] with A[j]

翻译自: https://www.freecodecamp.org/news/quickselect-algorithm-explained-with-examples/

quickselect