排序算法（快排+推排序+归并排序）

一、快排（不稳定+O(NlogN)）

分治思想，随机选一个数作为pivot，然后放到数组最后去，比这个元素小的放左边，比这个元素大的放右边。最后再交换左边放完后的下一个元素和pivot，这样就把一个元素排好序了，然后再递归把下一个元素排好序就可以了。

class Solution {public int[] sortArray(int[] nums) {quicksort(nums, 0, nums.length - 1);return nums;}public void quicksort(int[] nums, int left, int right) {if (left < right) {int pos = partition(nums, left, right);//找到分区点quicksort(nums, left, pos - 1);quicksort(nums, pos + 1, right);}}public int partition(int[] nums, int left, int right) {int randomindex = new Random().nextInt(right - left + 1) + left;//将随机数的范围从相对偏移转换为绝对位置swap(nums, randomindex, right);int pivot = nums[right];int i = left - 1;//标记“小于等于基准值”的子数组的边界for (int j = left; j < right; j++) {if (nums[j] <= pivot) {i++;swap(nums, i, j);}}swap(nums, i + 1, right);return i + 1;}public void swap(int[] nums, int i, int j) {int temp = nums[i];nums[i] = nums[j];nums[j] = temp;}
}

二、堆排序(O(NlogN))

堆其实是一个完全二叉树，根据堆的特性可以分为大根堆和小根堆，若节点下标为i，则左子节点下标为2i+1，右子节点下标为2i+2

用大根堆排序完的序列是正序的（递增）<先初始化一个大根堆，再交换元素>

用小根堆排序完的序列是倒序的（递减）

三、前K个高频元素

class Solution {public int[] topKFrequent(int[] nums, int k) {Map<Integer, Integer> map = new HashMap<>();for (int i = 0; i < nums.length; i++) {map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);}PriorityQueue<int[]> pq = new PriorityQueue<>((pair1, pair2) -> pair1[1] - pair2[1]);for (Map.Entry<Integer, Integer> entry : map.entrySet()) {//遍历每一个键值对if (pq.size() < k) {pq.add(new int[] { entry.getKey(), entry.getValue() });} else {if (entry.getValue() > pq.peek()[1]) {pq.poll();pq.add(new int[] { entry.getKey(), entry.getValue() });}}}int[] result = new int[k];for (int i = k - 1; i >= 0; i--) {result[i] = pq.poll()[0];}return result;}
}

四、数组中的第K个最大元素

使用优先级队列（数组中前k个高频元素简化版）

class Solution {public int findKthLargest(int[] nums, int k) {PriorityQueue<Integer> pq = new PriorityQueue<>();for(int num:nums){if(pq.size()<k){pq.add(num);}else{if(num>pq.peek()){pq.poll();pq.add(num);}}}return pq.peek();}
}

手撕时要自己构建一个堆

最后一个非叶子节点的索引是 heapsize/2-1

class Solution {public int findKthLargest(int[] nums, int k) {int heapsize = nums.length;buildmaxheap(nums,heapsize);for(int i = 0;i<k-1;i++){swap(nums,0,heapsize-1);heapsize--;maxheapify(nums,0,heapsize);}return nums[0];}public void buildmaxheap(int[] nums, int heapsize){for(int i = heapsize/2-1;i>=0;i--){maxheapify(nums,i,heapsize);}}public void maxheapify(int[] nums,int i,int heapsize){int left = 2*i +1,right = 2*i+2,largest = i;if(left<heapsize&&nums[left]>nums[largest]){largest=left;}if(right<heapsize&&nums[right]>nums[largest]){largest=right;}if(largest!=i){swap(nums,i,largest);maxheapify(nums,largest,heapsize);}}public void swap(int[] nums,int i,int j){int temp = nums[i];nums[i] = nums[j];nums[j] = temp;}
}