215.数组中的第K个最大元素(堆排，快排)

给定整数数组 nums 和整数 k，请返回数组中第 k个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4 输出: 4

1. 快排。唯一要注意的地方就是退出函数的条件，当待排序数组只有一个元素(k=1)，那么结果就是它。这里没有考虑剪枝，即当前这一轮排序后确定的位置如果正好是第k个大的数字，则可以直接退出返回，不必进行到只剩一个元素待排序数组的情况。

public int quicksort(int[] nums,int low,int high,int k)
    {
        //if(low>=high)
        //return ;
        if(low==high)
        return nums[high];
        int base=nums[low];
        int left=low,right=high;
        while(low<high)
        {
            while(low<high&&nums[high]>=base)
            high--;
            while(low<high&&nums[low]<=base)
            low++;
            if(low<high)
            {
                int temp=nums[high];
                nums[high]=nums[low];
                nums[low]=temp;
            }
        }//这里循环出来必定有low=high
        nums[left]=nums[high];
        nums[high]=base;
        //quicksort(nums,left,low-1);
        //quicksort(nums,high+1,right);
        if(right-high>=k)
        return quicksort(nums,high+1,right,k);
        else
        return quicksort(nums,left,high,k-(right-high));

    }

2. 堆排序。整个堆排序巧妙的地方在于，大根堆的排序和每轮排序后结果(堆顶元素)都是保存在一个数组中。排序过程中堆空间变小，排序后的有序数组空间变大。因此自顶向下调整堆时，maxHeapify()的形参中要包含当前所要调整的堆的大小。其它要考虑清楚的就以下几点：

• 顺序存储的二叉树左孩子和右孩子表示方式。
• 堆调整时左孩子或者右孩子越界的限制条件。
• 初始堆时从哪个位置开始调整。

    public int findKthLargest(int[] nums, int k) {
       buildMaxHeap(nums);
       int heapsize=nums.length;
       for(int i=0;i<k;i++)
       {
           swap(nums,0,nums.length-1-i);
           heapsize--;    //排序完一轮堆大小减1
           maxHeapif(nums,0,heapsize);
       }
       return nums[nums.length-k];     
    }
    public void buildMaxHeap(int[] nums) //初始堆
    {
        for(int i=(nums.length-1)/2;i>=0;i--)
            maxHeapif(nums,i,nums.length);
    }
    public void maxHeapif(int[] nums,int target,int heapsize)
    {
        int left=target*2+1,right=target*2+2,max=target;
        if(left<heapsize&&nums[max]<nums[left])
        max=left;
        if(right<heapsize&&nums[max]<nums[right])
        max=right;
        if(max==target) //满足堆定义返回
        return;
        swap(nums,target,max);
        maxHeapif(nums,max,heapsize);
    }