堆排序做的，没有全部排序，找到第k个就结束

public int findKthLargest(int[] nums, int k) {
int num = 0;
if (nums.length <= 1) return nums[0]; int heapSize = nums.length; //1.构建最大堆 int half = (heapSize-2)/2; for (int i = half;i >= 0;i--)
{
adjust(nums,heapSize,i);
}
while (heapSize > 1)
{
//2.取出最大值
swap(0,heapSize-1,nums);
heapSize--;
num++;
if(num == k)
break;
//3.调整堆
adjust(nums,heapSize,0);
}
return nums[nums.length-k];
}

public void adjust(int\[\] nums,int heapSize,int index)  
{  
    int left = index\*2+1;  
    int right = index\*2+2;  
    int biggest = index;  
    if (left < heapSize && nums\[left\] > nums\[biggest\])  
        biggest = left;  
    //注意这里都是和nums\[biggest\]比较，别写成index，因为要找出最大的值  
    if (right < heapSize && nums\[right\] > nums\[biggest\])  
        biggest = right;  
    if (biggest != index)  
    {  
        swap(index,biggest,nums);  
        adjust(nums,heapSize,biggest);  
    }  
}  
public void swap(int a,int b,int\[\] nums)  
{  
    int temp = nums\[a\];  
    nums\[a\] = nums\[b\];  
    nums\[b\] = temp;  
}

堆排序的算法时间复杂度是：O（n*log k ）

下边快排的改进做法，O（n）

利用快速排序的思想，从数组S中随机找出一个元素X，把数组分为两部分Sa和Sb。Sa中的元素大于等于X，Sb中元素小于X。这时有两种情况：

           1. Sa中元素的个数小于k，则Sb中的第k-|Sa|个元素即为第k大数；

           2. Sa中元素的个数大于等于k，则返回Sa中的第k大数。时间复杂度近似为O(n)

public void findk(int[] nums,int sta,int end,int k)
{
if (sta>end) return;
Random random = new Random();
int p = random.nextInt(end-sta)+sta;
swap(nums,p,sta);
int l = sta;
int r = end;
while (l=nums[sta])
r--;
while (l<r&&nums[l]<=nums[sta])
l++;
swap(nums,l,r);

    }  
    swap(nums,l,sta);  
    //记录右边数组(包括排序好的数)的大小  
    int size = end-l+1;  
    if (size == k) System.out.println(nums\[l\]);  
    else if (size<k) findk(nums,sta,l-1,k-size);  
    else findk(nums,l,end,k);  
}  
public void swap(int\[\] nums,int i ,int j)  
{  
    int temp = nums\[i\];  
    nums\[i\] = nums\[j\];  
    nums\[j\] = temp;  
}