【算法】快速选择算法

1.概述

（1）快速选择算法 (Quick Select Algorithm) 是一种用于在无序数组中寻找第 k 小（或第 k 大）元素的高效算法，它是快速排序算法的一个变种。快速选择算法的基本思想是通过每次选取一个枢纽元素（通常是随机选择或者选择第一个或最后一个元素），将数组划分为两个部分，并将枢纽元素放置在其最终的排序位置上。然后，根据枢纽元素的位置，判断第 k 小（或第 k 大）元素在数组的左半部分还是右半部分，并且递归地在相应的部分中查找。

（2）与快速排序不同的是，快速选择算法只需要递归处理数组的一半。这样，在平均情况下，算法的时间复杂度为 O(n)，其中 n 是数组的大小。然而，在最坏情况下，快速选择算法的时间复杂度可能达到 O(n²)，但这种情况的概率很低。

2.代码实现

实现快速选择算法有许多方式，下面将逐一介绍。需要注意的是，在下面的实现方式中，只有基于快速排序的快速选择算法的时间复杂度为 O(n)。此外，有关排序算法的具体知识可以参考【算法】内部排序这篇文章。

注意：下面的代码实现都是找出数组中的第 k 个最大元素。

2.1.基于简单交换排序

这里考虑利用简单交换排序的特点，即每完成一趟排序，就至少会有一个元素的位置确定，那么只需要对数组 nums 进行 k 躺降序排序，此时的 nums[k - 1] 必为数组 nums 中第 k 个最大的元素，将其返回即可。该算法的时间复杂度为 O(k * n)，具体实现代码如下：

class Solution {
    public int findKthLargest(int[] nums, int k) {
    	//进行 k 趟排序
        for (int i = 0; i < k; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] < nums[j]) {
                	//交换 nums[i] 和 nums[j]
                    int tmp = nums[i];
                    nums[i] = nums[j];
                    nums[j] = tmp;
                }
            }
        }
        return nums[k - 1];
    }
}

2.2.基于堆排序

我们可以使用堆排序来找出数组中的第 k 个最大元素，即建立一个大根堆，做 k − 1 次删除操作后堆顶元素就是我们要找的答案。在 Java 中，我们可以直接使用优先级队列来完成这一操作。当然，如果想更加了解推排序，我们也可以手动实现。该算法的时间复杂度为 O(nlogk)，具体代码如下：

//使用优先级队列
class Solution {
    public int findKthLargest(int[] nums, int k) {
        //创建一个大根堆
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
        //将数组中的元素加入堆
        for (int num : nums) {
            maxHeap.offer(num);
        }
        //进行 k - 1 次删除操作
        for (int i = 0; i < k - 1; i++) {
            maxHeap.poll();
        }
        //堆顶元素就是第 k 个最大元素
        return maxHeap.peek();
    }
}

//手动实现堆排序
class Solution {
    public int findKthLargest(int[] nums, int k) {
        int length = nums.length;
        //循环建立初始堆，调用 sift 算法 ⌊n / 2⌋ 次
        for (int i = (length - 1) / 2; i >= 0; i--) {
            sift(nums, i, length - 1);
        }
        for (int i = length - 1; i >= length - k; i--) {
            //将 nums[i] 与根 nums[0] 交换
            int tmp = nums[0];
            nums[0] = nums[i];
            nums[i] = tmp;
            //对 nums[0...i - 1] 进行筛选，得到 i 个节点的堆
            sift(nums, 0, i - 1);
        }
        return nums[length - k];
    }

    //对 nums[low...high] 进行筛选，使得以 nums[low] 为根节点的左子树和右子树均为大根堆
    public void sift(int[] nums, int low, int high) {
        // nums[j] 是 nums[i] 的左孩子
        int i = low;
        int j = (i == 0) ? 1 : 2 * i;
        int tmp = nums[i];
        while (j <= high) {
            //如果右孩子更大，则将 j 指向右孩子
            if (j < high && nums[j] < nums[j + 1]) {
                j++;
            }
            //根节点小于最大孩子节点
            if (tmp < nums[j]) {
                nums[i] = nums[j];
                nums[j] = tmp;
                i = j;
                j = 2 * i;
            } else {
                //如果跟节点大于等于最大孩子关键字，筛选结束
                break;
            }
        }
    }
}

2.3.基于快速排序

具体实现思路如下：

首先定义一个函数 findKthLargest，该函数接收一个数组 nums 和一个整数 k，返回该数组中第 k 大的元素。
在 findKthLargest 函数中，调用 quickSelect 函数进行快速选择，在数组 nums 的下标范围 [left, right] 中查找第 index 大的元素。
在 quickSelect 函数中，首先调用 randomPartition 函数进行随机划分，得到基准元素的下标 q：
- 判断 q 是否等于 index，如果相等则说明已经找到了第 k 大的元素，直接返回 nums[q]。
- 如果 q 不等于 index，根据 q 在 [left, right] 中与 index 的大小关系，递归调用 quickSelect 函数查找第 k 大的元素。如果 q < index，则第 k 大的元素在右区间，递归调用 quickSelect(nums, q + 1, right, index)；否则第 k 大的元素在左区间，递归调用 quickSelect(nums, left, q - 1, index)。
randomPartition 函数采用随机选择基准元素的方法，将一个下标 i 转换成基准元素，使得 [left,i-1] 中的所有元素都小于等于基准元素，[i+1, right] 中的所有元素都大于等于基准元素，并返回基准元素的下标。
partition 函数是快速排序中划分数组的核心操作，它以 nums[left] 为基准，将数组 nums[left…right] 划分为两个子数组 nums[left…i-1] 和 nums[i+1…right]，并返回最终元素 nums[left] 所在的下标 i。此处实现的是双指针的快速排序实现方式。

class Solution {
    Random random = new Random();

    public int findKthLargest(int[] nums, int k) {
        //第 K 个最大元素其实就是升序排序后的元素 nums[nums.length - k]
        return quickSelect(nums, 0, nums.length - 1, nums.length - k);
    }
    
    public int quickSelect(int[] nums, int left, int right, int index) {
        int q = randomPartition(nums, left, right);
        if (q == index) {
            //当前划分的下标 q 等于 index，则说明这次划分操作后已经找到了第 k 个最大元素，其下标为 q，直接返回 nums[q] 即可
            return nums[q];
        } else {
            /*
                当前划分的下标 q 不等于 index: 
                (1) 如果 q < index，那么则说明第 k 个最大元素在右区间，此时递归右区间
                (2) 如果 q > index，那么则说明第 k 个最大元素在左区间，此时递归左区间
            */
            if (q < index) {
                return quickSelect(nums, q + 1, right, index)
            } else {
                return quickSelect(nums, left, q - 1, index);
            }
        }
    }
    
    public int randomPartition(int[] nums, int left, int right) {
        // random.nextInt(int num): 随机返回一个 [0, num) 内的整数
        int i = random.nextInt(right - left + 1) + left;
        int tmp = nums[i];
        nums[i] = nums[left];
        nums[left] = tmp;
        return partition(nums, left, right);
    }
    
    //以 nums[left] 为基准，进行一趟划分并返回最终元素 nums[left] 所在的下标
    private int partition(int[] nums, int left, int right) {
        int i = left, j = right;
        //以 nums[left] 为基准
        int benchmark = nums[left];
        while (i < j) {
            //从右向左扫描，找到一个小于 benchmark 的元素 nums[j]
            while (i < j && benchmark <= nums[j]) {
                j--;
            }
            nums[i] = nums[j];
            //从左向右扫描，找到一个大于 benchmark 的元素 nums[i]
            while (i < j && nums[i] <= benchmark) {
                i++;
            }
            nums[j] = nums[i];
        }
        nums[i] = benchmark;
        return i;
    }
}

3.应用

（1）快速选择算法在处理数组中第 k 大/小元素的问题上具有广泛的应用场景。以下是一些应用场景的示例：

数组中的第 k 大/小元素：快速选择算法可以在线性时间复杂度内找到数组中的第 k 大/小元素。这在需要找到排名靠前/靠后的元素时非常有用，例如找到数组中的中位数或前 k 个最大的元素。
排序问题：在快速排序算法中，使用快速选择算法找到基准元素的位置，然后通过递归地对基准元素左右两部分进行排序，最终实现对整个数组的排序。
基于中位数的分割问题：在一些分割问题中，我们可以使用快速选择算法找到数组的中位数，并将数组分割成两个部分。这在一些分治算法中非常常见，例如快速排序、快速选择等。
统计问题：快速选择算法可用于解决一些统计问题，例如找到数组中出现次数最多的元素、找到更大/更小的元素等。