前言 这个题很经典，可以对快速排序或者堆排序进行改装，就可以以O(n)的平均时间复杂度解决
思路 1、快速排序 快速排序的核心思想：以数组最后一个数作为标杆，所有比其小的数移动至其右边，比其大的数移动至左边，核心代码如下：
public int partition(int[] nums,int l,int r){ int x = nums[r]; int i = l-1; //(nums); for(int j = l;j<=r;j++){ if(nums[j]<=x){ //swap int tmp = nums[++i]; nums[i] = nums[j]; nums[j] = tmp; } } //print(nums); return i; }利用图解的方式如下：
利用递归的思想，如果partition得到的位置i大于target，则向左递归，反之则向右递归，直到i==target时返回。为了防止极端情况的发生，引入了随机因素，即，选择任意位置和最后位置的数进行交换，整体代码为：
class Solution { Random random = new Random(); public int randomPartition(int[] a,int l,int r){ int i = random.nextInt(r - l + 1) + l; swap(a, i, r); return partition(a, l, r); } int quikSelect(int[] nums,int l,int r,int target){ int q = randomPartition(nums,l,r); if(q==target){ return nums[q]; } return (q>target?quikSelect(nums,l,q-1,target):quikSelect(nums,q+1,r,target)); } public int partition(int[] nums,int l,int r){ int x = nums[r]; int i = l-1; //(nums); for(int j = l;j<=r;j++){ if(nums[j]<=x){ //swap int tmp = nums[++i]; nums[i] = nums[j]; nums[j] = tmp; } } //print(nums); return i; } void print(int[] nums){ for(int i = 0;i<nums.length;i++){ System.out.print(nums[i]+" "); } System.out.println(); } public int findKthLargest(int[] nums, int k) { return quikSelect(nums,0,nums.length-1,nums.length-k); } public void swap(int[] a, int i, int j) { int temp = a[i]; a[i] = a[j]; a[j] = temp; } }2、堆排序 思想很简单，就是建立一个大顶堆，然后进行若干次的删除操作，最后得到的堆顶就是我们想要的结果，这里着重说明在不使用库中的类，自己如何实现一个大顶堆。
1） 建堆 完全二叉树的定义： 一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。
由于堆是一颗完全二叉树，其最后一个父节点一定位于（heapsize-1）/2的位置处，其左、右子节点一定位于2i+1和2i+2处（i为父节点的位置），因此在建堆的过程可以从数组的父结点出发，递归的和子节点进行交换，使小的父节点沉下去。
void buildHeap(int[] nums,int heapSize){ int i = (heapSize-1)/2; for(int j = i;j>=0;j--){ //堆调整 maxHeap(nums,j,heapSize); } } void maxHeap(int[] num,int i,int heapSize){ //这里返回的条件可以省略 if(i>=heapSize){ return; } int left = 2*i+1; int right = 2*i+2; int largest = i; if(left<heapSize&&num[left]>num[largest]){ largest = left; } if(right<heapSize&&num[right]>num[largest]){ largest = right; } if(largest!=i){ //i与largest对掉，并进行递归操作 swap(num, i, largest); maxHeap(num, largest, heapSize); } }2）删除操作 删除操作可以理解为将堆的最底层的数和最高层的数互换，然后将堆的大小减一，最后再进行堆的调整
总体代码块：
class Solution { public int findKthLargest(int[] nums, int k) { int heapSize = nums.length; buildHeap(nums,heapSize); // for(int i = 0;i<heapSize;i++){ // System.out.print(nums[i]+" "); // } System.out.println(); int result = 0; while(k-->0){ result = pop(nums,heapSize); //System.out.println("第"+k+"个："+result); --heapSize; } return result; } void buildHeap(int[] nums,int heapSize){ int i = (heapSize-1)/2; for(int j = i;j>=0;j--){ //堆调整 maxHeap(nums,j,heapSize); } } void maxHeap(int[] num,int i,int heapSize){ //这里返回的条件可以省略 if(i>=heapSize){ return; } int left = 2*i+1; int right = 2*i+2; int largest = i; if(left<heapSize&&num[left]>num[largest]){ largest = left; } if(right<heapSize&&num[right]>num[largest]){ largest = right; } if(largest!=i){ //i与largest对掉，并进行递归操作 swap(num, i, largest); maxHeap(num, largest, heapSize); } } //堆的弹出操作,弹出操作会使得堆的大小缩减 int pop(int[] num,int heapSize){ if(heapSize==0){ System.out.println("Should not be here"); } int result = num[0]; swap(num,0,heapSize-1); maxHeap(num,0,heapSize-1); return result; } void swap(int[] num,int i,int j){ int tmp = num[i]; num[i] = num[j]; num[j] = tmp; } }