题目：
在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
题解：
当看到TOP K问题时，脑海中应立马想到堆排序。以这个题目来回顾下排序算法。在回顾排序算法前，我们来回顾下几个术语：时间复杂度、空间复杂度、稳定性。稳定性的定义我们容易忘记，下面来回顾下它的定义：
前提条件：a=b的情况下,若在未排序时a在b前面，在已排序后a仍在b前面，那么这个算法就是稳定的；否则就是不稳定的。
1：冒泡排序：两两比较，交换小的数和大的数的位置。
时间复杂度：最好O(N)，最坏O(N²)，平均O(N²) ；空间复杂度：O(1)；是否稳定：稳定
public void bubbleSort(int[] nums){ for(int i=0;i<=nums.length-2;i++){ for(int j=i+1;j<=nums.length-1;j++){ if(nums[j] < nums[i]){ int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp; } } } }
若数组是有序的，可以用flag标志位来判断是否排序过。
//O(N) 若元素已有序，那么借助flag判断是否有序 public void bubbleSort2(int[] nums){ for(int i=0,flag = 0;i<=nums.length-2;i++){ for(int j=i+1;j<=nums.length-1;j++){ if(nums[j] < nums[i]){ int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp; flag = 1;//表示已排序过，原数组不是有序的 } } if(flag == 0) break; } }
2.选择排序：从前往后一次找到未排序过元素的最小值，然后依次填入第0个位置、第1个位置、第2个位置。。。
时间复杂度：最好O(N²)，最坏O(N²)，平均O(N²) ；空间复杂度：O(1)；是否稳定：不稳定
public static void selectSort(int[] nums){ //首先选择最小的数字放在第0个位置 //再选择剩余数字最小的数字放在第1个位置 //... for(int i=0;i<=nums.length-1;i++){ int idx = i;//当前最小数的下标 int min = nums[idx]; //找到最小的数填充第i个位置 for(int j=i+1;j<=nums.length-1;j++){ if(nums[j] < min){ min = nums[j]; idx = j; } } //若找到了更小的数，则交换位置 if(idx > i){ int tmp = nums[i]; nums[i] = nums[idx]; nums[idx] = tmp; } } }
3.快速排序：首先选择一个基准数x，它的位置（坑位）是i，然后先从后向前找比x小的数（所在位置是j）填这个基准数所在的坑位i，然后从左向右找比x大的数填这个新的坑位j。交替进行。
时间复杂度：最坏（数组已排序）O(N²)，最好O(nlogN)，平均O(nlogN) ； 空间复杂度 O(1)；是否稳定：不稳定
//1.快速排序（分治法） public static void quickSort(int l,int r,int[] nums){ if(l < r){ int x = nums[l]; int i = l, j = r; while(i < j){ //从后向前找比x小的数 while(i < j && nums[j] >= x) j--; if(i < j){ nums[i] = nums[j]; i++; } //从前向后找比x大的数 while(i < j && nums[i] < x){ i++; } if(i < j){ nums[j] = nums[i]; j--; } } //最后i=j nums[i] = x; //分治法 quickSort(l,i-1,nums); quickSort(i+1,r,nums); } }
4.堆排序：堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。它有非常重要的三步：
1.建堆
2.调整堆，使得堆符合大（小）顶堆的性质
3.删除已排序的数，即数组新的最后一个元素已经排好序了，下次调整堆不要调整这个数了。当把堆顶元素与最后一个元素交换后，大的元素都在数组后面。交换后堆顶元素发生了变化，需要重新调整堆。
时间复杂度：最坏O(NlogN)，最好O(NlogN)，平均O(NlogN)；空间复杂度：O(1)。建堆的时间复杂度是O(N)，调整堆的时间复杂度是O(logN)；是否稳定：不稳定
下面上代码（也是本题的解法）：
class Solution { public int findKthLargest(int[] nums, int k) { heapSort(nums); //quickSort(nums,0,nums.length - 1); //bubble(nums); //selectSort(nums); //for(int p: nums) System.out.println(p); return nums[nums.length-k]; } //冒泡算法 public void bubble(int[] nums){ for(int i=0;i<=nums.length-2;i++){ for(int j=i+1;j<=nums.length-1;j++){ if(nums[j] < nums[i]){ int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp; } } } } //选择排序（冒泡排序的改版） public void selectSort(int[] nums){ for(int i=0;i<nums.length;i++){ int min = nums[i]; int idx = i; for(int j=i+1;j<nums.length;j++){ if(nums[j] < min){ min = nums[j]; idx = j; } } int tmp = nums[i]; nums[i] = nums[idx]; nums[idx] = tmp; } } //快速排序 public void quickSort(int[] nums, int l, int r){ if(l < r){ int x = nums[l]; int i= l, j = r;//l r 是分治法的左右边界 while(i < j){ //从右到左找比x小的数 while(i < j && nums[j] >= x) j--; if(i < j){ nums[i] = nums[j]; i++; } //从左到右找比x大的数 while(i < j && nums[i] < x) i++; if(i < j){ nums[j] = nums[i]; j--; } nums[i] = x; quickSort(nums,l,i-1); quickSort(nums,i+1,r); } } } //堆排序 public void heapSort(int[] nums){ buildHeap(nums); //将大堆顶元素与末尾元素交换，堆顶的元素就放在数组后面了，然后再维护剩下的堆 for(int i=nums.length-1;i>=0;i--){ swap(nums,i,0); //交换后需要重新维护大顶堆的性质 adjustHeap(0,nums,i);//最后一个元素已经排好序了，不需要再调整了，即需要调整的元素的个数为i，相当于删除了最后一个元素 } } //建堆 public void buildHeap(int[] nums){ for(int i=nums.length/2 -1;i>=0;i--){ //维护堆的位置 adjustHeap(i,nums,nums.length); } } //i 根节点 public void adjustHeap(int i,int[] nums, int len){ int l = 2 * i + 1, r = 2 * i +2; int largestIdx = i;//默认根节点是最大的节点 // l < len 防止越界 if(l < len && nums[largestIdx] < nums[l]){ largestIdx = l; } if(r < len && nums[largestIdx] < nums[r]){ largestIdx = r; } if(largestIdx != i){ //交换位置 swap(nums,i,largestIdx); //交换后需要重新维护大顶堆的性质 adjustHeap(largestIdx,nums,len); } } public void swap(int[] nums,int i,int j){ int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp; } }