快速选择算法

1.二叉堆2.快速选择算法

2.1回顾快速排序算法2.2快速选择算法 总结

思路：将节点一个一个的插入二叉堆（优先队列），当堆中元素多于k个时，删除堆顶元素。每个节点都过一遍之后，再取堆顶元素。

public int findKthLargest(int[] nums, int k) {
        PriorityQueue que = new PriorityQueue<>();
        for (int num : nums) {
            que.offer(num);
            if (que.size()>k){
                que.poll();
            }
        }
        return que.peek();
    }

public void sort(int[] nums) {
        quickSort(nums, 0, nums.length - 1);
    }

    public void quickSort(int[] nums, int lo, int hi){
        if (hi<=lo) return;
        int partition = partition(nums, lo, hi);

        quickSort(nums,lo,partition-1);
        quickSort(nums,partition+1,hi);
    }

    public int partition(int[] nums, int lo, int hi){
        int pivot = nums[lo];
        int i =lo;
        int j = hi+1;
        while (true){
            while (nums[++i]pivot){
                if (j==lo) break;
            }

            if (i>=j) break;

            swap(nums,i,j);
        }
        swap(nums,lo,j);
        return j;
    }

    public void swap(int[] nums,int i,int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

public int findKthLargest(int[] nums, int k) {
        k = nums.length - k;
        int lo = 0, hi = nums.length - 1;
        while (lo<=hi){
            int partition = partition(nums, lo, hi);
            if (partitionk){
                hi = partition - 1;
            }else {
                return nums[partition];
            }
        }
        return -1;
    }

遇到题目优先选择二叉堆，快速排序算法熟记