基于快速排序：如何在O(n)时间内，找到一个无序数组的第K大元素？

如何在O(n)时间内，找到一个无序数组的第K大元素？

              基本思路：利用快排的思想，将无序数组array[]【左下标l，右下标r】分为三个区间，【小于第k个元素】、【等于第k个元素】、【大于第k个元素】，选取一个基准值的下标p与k相比，若比k大，则继续在【l，p-1】之间递归，若比k小，则在【p+1，r】之间递归。
 

平均时间复杂度：O(n+n/2+n/4+...+1) = O(n)

import java.util.Scanner;

public class QuickSortInternalPractice {
    
       //在O(n)时间复杂度里找到一个无序数组的第k大元素
    public static void findK(int[] array) {
        int n = array.length;
        if (n <= 1) {
            return;
        }
        int k = new Scanner(System.in).nextInt() - 1;
        method(array, 0, n - 1, k);
    }

    public static void method(int[] array, int l, int r, int k) {
        if (k < l || k > r) {
            throw new IndexOutOfBoundsException("索引越界异常！");
        }
        if (l > r) {
            return;
        }
        int randomIndex = (int) Math.random() * (r - l + 1) + l;
        swap(array,l,randomIndex);
        int p = partition3(array, l, r);
        if (p > k) {
            method(array, l, p - 1, k);
        } else if (p < k) {
            method(array, p + 1, r, k);
        } else {
            System.out.println(array[p]);
        }
    }

    public static int partition3(int[] array, int l, int r) {
        int val = array[l];
        int j = l;
        int i = l + 1;
        for (; i <= r; i++) {
            if (array[i] < val) {
                swap(array, j + 1, i);
                j++;
            }
        }
        swap(array, l, j);
        return j;
    }

}