如何实现快速选择算法？

快速选择算法(Quickselect)是一种在数组中查找第K大元素的算法。它与快速排序算法非常相似,只是找到第K大元素后就停止递归。

我们可以实现快速选择算法如下:

public int quickselect(int[] nums, int k) {
    return quickselect(nums, 0, nums.length - 1, k);
}

private int quickselect(int[] nums, int left, int right, int k) {
    // 1. 递归终止条件
    if (left == right) return nums[left];

    // 2. 选择pivot并划分数组
    int pivotIndex = partition(nums, left, right);

    // 3. 确定K属于左部分或右部分
    if (k <= pivotIndex - left) 
        return quickselect(nums, left, pivotIndex - 1, k);
    else
        return quickselect(nums, pivotIndex + 1, right, k - (pivotIndex - left + 1)); 
}

private int partition(int[] nums, int left, int right) {
    int pivot = nums[left];
    int j = left;
    for (int i = left + 1; i <= right; i++) {
        if (nums[i] < pivot) {
            j++;
            swap(nums, j, i);
        }
    }
    swap(nums, left, j);
    return j;
}

private void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

算法流程:

1. 递归终止:当left == right,找到第K大元素。
2. 选择pivot并划分数组,返回pivot位置index。
3. 判断K属于左部分或右部分,递归查找。
4. 不断划分数组并递归,直到找到第K大元素。

时间复杂度O(n),空间复杂度O(logn)。

所以,快速选择算法的关键是:

1. 使用快速排序中的pivot选取与划分数组方法。
2. 递归终止条件:left == right。
3. 判断k属于左部分或右部分,相应递归。
4. 通过不断划分数组和递归,找到第k大元素。

与快速排序算法相比,找到第K大元素后直接返回,不继续递归划分与排序。