最近看完算法4第二章排序后，根据CyC大佬的leetcode刷题题解，对LeetCode中的排序题目作了以下总结：

堆排序：

LeetCode215： 题目描述：

找到未排序数组中的第k个最大元素。请注意，它是排序顺序中的第k个最大元素，而不是第k个不同元素。

Input: [3,2,1,5,6,4] and k = 2  Output: 5
Input: [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<Integer> 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);
            }
        }

桶排序

LeetCode347. Top K Frequent Elements (Medium) 找出出现频率最多的 k 个数

题目描述：

给定非空的整数数组，返回k个最常见的元素。

Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

Input: nums = [1], k = 1
Output: [1]

解决方法：

设置若干个桶，每个桶存储出现频率相同的数，并且桶的下标代表桶中数出现的频率。

class Solution {
        public List<Integer> topKFrequent(int[] nums, int k) {
            Map<Integer,Integer> map = new HashMap<>();
            for(int a : nums){
                map.put(a,map.getOrDefault(a,0)+1);//判断a是否存在，如果没出现
                
            }
            List<Integer> [] 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<Integer> 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;
        }
    }

荷兰国旗问题：

LeetCode75. Sort Colors (Medium)

题目描述：

给定一个具有红色，白色或蓝色的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;
        }
    }