本文共 4578 字，大约阅读时间需要 15 分钟。
最近看完算法4第二章排序后，对LeetCode中的排序题目作了以下总结：
题目描述：
找到未排序数组中的第k个最大元素。请注意，它是排序顺序中的第k个最大元素，而不是第k个不同元素。
Input: [3,2,1,5,6,4] and k = 2 Output: 5Input: [3,2,3,1,2,4,5,5,6] and k = 4 Output: 4
解题方法：
1、对整个输入数组进行排序，然后通过它的索引（即O（1））操作访问该元素：
时间复杂度 O(NlogN)，空间复杂度 O(1)。
public int findKthLargest(int[] nums, int k) { final int N = nums.length; Arrays.sort(nums); return nums[N - k]; } 2、堆排序也可以用于求解 Kth Element 问题，堆顶元素就是 Kth Element。使用面向最小值的优先级队列来存储第K个最大值。该算法迭代整个输入并维持优先级队列的大小。优先队列可以用堆来实现：
时间复杂度 O(NlogK)，空间复杂度 O(K)。
public int findKthLargest(int[] nums, int k) { PriorityQueue pq = new PriorityQueue<>(); // 小顶堆 for (int val : nums) { pq.add(val); if (pq.size() > k) // 维护堆的大小为 K pq.poll(); } return pq.peek(); } 3、基于切分partion的快速选择算法；快速排序的 partition() 方法，会返回一个整数 j 使得 a[l…j-1] 小于等于 a[j]，且 a[j+1…h] 大于等于 a[j]，此时 a[j] 就是数组的第 j 大元素。可以利用这个特性找出数组的第 k 个元素。
时间复杂度 最佳情况：O(N) 最坏情况：O（N ^ 2），空间复杂度 O(1)
我们如何才能改进上述解决方案并使其保证O（N）？答案非常简单，刚开始时要对数组进行洗牌shuffle，使其随机化输入，这样即使提供最坏情况输入，算法也不会受到影响。因此，所需要做的就是改变输入。
public int findKthLargest(int[] nums, int k) { shuffle(nums);//打乱数组 k = nums.length - k; int lo = 0; int hi = nums.length - 1; while (lo < hi) { final int j = partition(nums, lo, hi); if(j < k) { lo = j + 1; } else if (j > k) { hi = j - 1; } else { break; } } return nums[k]; } //切分 private int partition(int[] a, int lo, int hi) { int i = lo; int j = hi + 1; while(true) { while(i < hi && less(a[++i], a[lo])); while(j > lo && less(a[lo], a[--j])); if(i >= j) { break; } exch(a, i, j); } exch(a, lo, j); return j; } //交换 private void exch(int[] a, int i, int j) { final int tmp = a[i]; a[i] = a[j]; a[j] = tmp; } //比较是否小于 private boolean less(int v, int w) { return v < w; } private void shuffle(int a[]) { final Random random = new Random(); for(int ind = 1; ind < a.length; ind++) { final int r = random.nextInt(ind + 1); exch(a, ind, r); } } 找出出现频率最多的 k 个数
题目描述：
给定非空的整数数组，返回k个最常见的元素。
Input: nums = [1,1,1,2,2,3], k = 2Output: [1,2]Input: nums = [1], k = 1Output: [1]
解决方法：
设置若干个桶，每个桶存储出现频率相同的数，并且桶的下标代表桶中数出现的频率。
class Solution { public List topKFrequent(int[] nums, int k) { Map map = new HashMap<>(); for(int a : nums){ map.put(a,map.getOrDefault(a,0)+1); //判断a是否存在，如果没出现 } List [] buckets = new ArrayList[nums.length + 1]; for(int i : map.keySet()){ int frequency = map.get(i); if(buckets[frequency]==null){ buckets[frequency] = new ArrayList<>(); } buckets[frequency].add(i); } List topK = new ArrayList<>(); //从后向前遍历桶，最先得到的 k 个数就是出现频率最多的的 k 个数 for(int i = buckets.length - 1; i >= 0 && topK.size() < k;i--){ if(buckets[i]!=null){ topK.addAll(buckets[i]); } } return topK; } } 题目描述：
给定一个具有红色，白色或蓝色的n个对象的数组，对它们进行就地 排序，使相同颜色的对象相邻，颜色顺序为红色，白色和蓝色。
这里，我们将使用整数0,1和2分别表示红色，白色和蓝色。
注意： 您不应该使用库的排序功能来解决此问题。
Input: [2,0,2,1,1,0]Output: [0,0,1,1,2,2]
解决方法：
使用三向切分快速排序，将数组分成三个区间：等于红色、等于白色、等于蓝色。
class Solution { public void sortColors(int[] nums) { int zero = 0; int two = nums.length - 1; int one = 0; while(one <= two){ if (nums[one] == 0){ swap(nums,zero++,one++); //从前面开始交换的已经比较过了 }else if (nums[one] == 2){ swap(nums,two--,one); //这里注意one不要++，从后面交换到前面的还无法比较 }else { one++; } } } private static void swap(int [] nums,int a,int b){ int i = nums[a]; nums[a] = nums[b]; nums[b] = i; } } 转载地址：http://nerwi.baihongyu.com/