经典算法：快速选择算法

正经程序员 2023-01-26 15 1

前言

快速选择算法是一种选择算法，用于在无序列表中查找第K个最小元素。这个算法和快速排序算法有关。它在实际应用是一种高效的算法，具有很好的平均时间复杂度，最坏的时间复杂度非常不理想。快速选择及其变种是实际应用中最常使用的高效选择算法。

例如：

输入： [7, 4, 6, 3, 9, 1] k = 2

输出： 第 k' 个最小的数组元素是 3

输入： [7, 4, 6, 3, 9, 1] k = 1

输出： k'第一个最小的数组元素是 1

快速选择的总体思路与快速排序一致，选择一个元素作为基准来对元素进行分区，将小于和大于基准的元素分在基准左边和右边的两个区域。

但是，不像在快速排序中那样递归到两侧，快速选择算法只递归到带有搜索元素的一侧。由于中心处于其最终排序位置，因此在它之前的所有那些都以未排序的顺序，而在它之后的所有那些都以未排序的顺序。

这将平均情况复杂度从O(n.log(n))降低到O(n)，最坏情况为O(n 2 )，其中n是输入的大小。

与快速排序一样，快速选择一般是以原地算法的方式实现，除了选出第k小的元素，数据也得到了部分地排序。

Java示例

import java.util.Arrays;
 
class GFG {
    public static int partition(int[] arr, int low,
                                int high)
    {
        int pivot = arr[high], pivotloc = low;
        for (int i = low; i <= high; i  ) {
            if (arr[i] < pivot) {
                int temp = arr[i];
                arr[i] = arr[pivotloc];
                arr[pivotloc] = temp;
                pivotloc  ;
            }
        }
 
        //将支点交换到最终的支点位置
        int temp = arr[high];
        arr[high] = arr[pivotloc];
        arr[pivotloc] = temp;
 
        return pivotloc;
    }
    public static int kthSmallest(int[] arr, int low,
                                  int high, int k)
    {
        // 找到分区
        int partition = partition(arr, low, high);
 
        // 如果分区值等于第 k 个位置，则返回 k 处的值。
        if (partition == k - 1)
            return arr[partition];
 
        // 如果分区值小于第 k 个位置，则搜索数组的右侧。
        else if (partition < k - 1)
            return kthSmallest(arr, partition   1, high, k);
 
        // 如果分区值大于第 k 个位置，则搜索数组的左侧。
        else
            return kthSmallest(arr, low, partition - 1, k);
    }
 
    public static void main(String[] args)
    {
        int[] array = new int[] { 10, 4, 5, 8, 6, 11, 26 };
        int[] arraycopy
            = new int[] { 10, 4, 5, 8, 6, 11, 26 };
 
        int kPosition = 3;
        int length = array.length;
 
        if (kPosition > length) {
            System.out.println("索引超出范围");
        }
        else {
            // 找到第 k 个最小值
            System.out.println(
                "第K个最小的元素是 : "
                  kthSmallest(arraycopy, 0, length - 1,
                              kPosition));
        }
    }
}

输出：第K个最小的元素是6