【算法训练-排序算法 二】【快速排序】数组中的第K个最大元素、最小的K个数

输入：
[1,3,5,2,2],5,3
返回值：
2

输入：
[10,10,9,9,8,7,5,6,4,3,4,2],12,3
返回值：
9
说明：
去重后的第3大是8，但本题要求包含重复的元素，不用去重，所以输出9

import java.util.*;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param a int整型一维数组
     * @param n int整型
     * @param K int整型
     * @return int整型
     */
    public int findKth (int[] a, int n, int K) {
        return quikSort(a, 0, n - 1, K);
    }
    public int quikSort(int[] a, int start, int end, int K) {
        // 找到基准元素的位置，这个位置是第 pivot+1(因为数组下标从0开始) 大的元素
        int pivot = partion(a, start, end);
        if (K == pivot + 1 ) {
            // 正好命中
            return a[pivot]  ;
        } else if (K < pivot + 1) {
            // K小于基准位置，说明它是更大的数，在基准位置左边搜索
            return quikSort(a, start, pivot - 1, K);
        } else {
            // K大于基准位置，说明它是更小的数，在基准位置右边搜索，
            return quikSort(a, pivot + 1, end, K );
        }
    }
    // 获取一个基准元素，倒排，所以大于基准元素的数在左，小于基准元素的数在右
    private int partion(int[] a, int start, int end) {
        int pivotValue = a[start];
        int i = start, j = end;
        while (i != j) {
            // (a[j]只有大于基准元素才停止，因为大的放基准元素左边
            while (a[j] <= pivotValue && i < j) {
                // 一定要j先走，因为j先走ij就会在j的位置交汇，而基准元素的左边一定要比自己大，所以为了保证后续基准元素交换正确，一定要保证交汇位置元素值大于等于基准元素，所以要优先满足j的条件（即找到大于基准元素的值并停下），如果i先走，在靠近交互点时，i会越过大于基准元素的值与j交汇。
                j--;
            }
            // (a[i]只有小于基准元素才停止，因为大的放基准元素左边
            while (a[i] >= pivotValue && i < j) {
                i++;
            }
            if (i < j) {
                swap(a, i, j);
            }
        }
        // 全部交换完后，基准元素交换
        swap(a, start, j);
        return j;
    }
    // 辅助函数，交换数组元素
    private void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

import java.util.*;
public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        // 1 入参判断，不满足条件返回空集合
        if (input.length == 0 || input.length < k) {
            return new  ArrayList<Integer>();
        }
        // 2 对数组进行快速排序
        quikSort(input, 0, input.length - 1);
        // 3 截断返回前k个最小的数
        int[] resultArray = Arrays.copyOf(input, k);
        ArrayList<Integer> result = new  ArrayList<Integer>();
        for (int value : resultArray) {
            result.add(value);
        }
        return result;
    }
    // 快速排序方法
    private void quikSort(int [] input, int left, int right) {
        int pivot;
        if (left < right) {
            pivot = partion(input, left, right);
            quikSort(input, left, pivot - 1);
            quikSort(input, pivot + 1, right);
        }
    }
    // 分治寻找基准值
    private int partion(int [] input, int left, int right) {
        // 1 随机打乱当前数组，均匀获取基准值下标
        int pivotIndex = new Random().nextInt(right - left + 1) + left;
        swap(input, left, pivotIndex);
        // 2 定义双指针
        int i = left;
        int j = right;
        int pivot = input[left];
        // 3 指针对撞交换
        while (i < j) {
            // 3-1 从右侧找到比基准值小的
            while (i < j && input[j] >= pivot ) {
                j--;
            }
            // 3-2 从左侧找到比基准值大的
            while (i < j && input[i] <= pivot ) {
                i++;
            }
            // 3-3 交换ij
            if (i < j) {
                swap(input, i, j);
            }
        }
        // 4 交换基准值与目标值
        swap(input, left, j);
        // 5 返回基准值索引下标
        return j;
    }
    private void swap(int [] input, int i, int j) {
        int temp = input[i];
        input[i] = input[j];
        input[j] = temp;
    }
}