LeetCode排序专题【算法】
风吹夏天 2020-06-08
快速选择
用于求解 Kth Element 问题，也就是第 K 个元素的问题。
可以使用快速排序的 partition() 分治进行实现。需要先打乱数组，否则最坏情况下时间复杂度为 O(N2)。
关于快速排序：
https://blog.csdn.net/nrsc272420199/article/details/82587933（例子和总结很好，是评论区说代码有问题0改成low，但是换成low我反而不理解了。。。嗷，理解了，后半段可能还需要分两段，后半段分两段后的前半段就不是从0开始了）
https://blog.csdn.net/morewindows/article/details/6684558 （这个也好理解，挖坑填数最后分治）
1个temp存第一个元素的数据作为基准数，排他！！！一个low指针的数据，还有一个high指针从尾部开始。
首先从后面hign指针开始，如果nums[high] 大于temp(后面没有值对应的变量名，用索引代替)，则high-1左移。若nums[high]小于temp则把nums[high]赋值给nums[low],即nums[low]=nums[high] ，赋值的话high不动不用左移！！ 是赋值给nums[low]不是temp！！！！temp是不变的一直是第一个元素的值！！！
前边nums[low]要是被后面小的nums[high]赋值以后的话，就要low指针右移1位，开始从前往后判断。如果此时low指针指向的元素小于nums[high]，则low指针继续右移。若nums[low]大于nums[high],则把nums[low]赋给nums[high],即nuns[high]=nums[low]，赋值操作low不用右移。
然后再开始从前往后遍历,直到low=high结束循环,此时low或high的下标就是基准数据23在该数组中的正确索引位置.
这样一遍走下来,可以很清楚的知道,其实快速排序的本质就是把基准数大的都放在基准数的右边,把比基准数小的放在基准数的左边,这样就找到了该数据在数组中的正确位置.
以后采用递归的方式分别对前半部分和后半部分排序，当前半部分和后半部分均有序时该数组就自然有序了。
堆
用于求解 TopK Elements 问题，也就是 K 个最小元素的问题。可以维护一个大小为 K 的最小堆，最小堆中的元素就是最小元素。最小堆需要使用大顶堆来实现，大顶堆表示堆顶元素是堆中最大元素。这是因为我们要得到 k 个最小的元素，因此当遍历到一个新的元素时，需要知道这个新元素是否比堆中最大的元素更小，更小的话就把堆中最大元素去除，并将新元素添加到堆中。所以我们需要很容易得到最大元素并移除最大元素，大顶堆就能很好满足这个要求。
堆也可以用于求解 Kth Element 问题，得到了大小为 k 的最小堆之后，因为使用了大顶堆来实现，因此堆顶元素就是第 k 大的元素。
快速选择也可以求解 TopK Elements 问题，因为找到 Kth Element 之后，再遍历一次数组，所有小于等于 Kth Element 的元素都是 TopK Elements。
可以看到，快速选择和堆排序都可以求解 Kth Element 和 TopK Elements 问题。
做过的一个 优先队列题378和一个我以为用优先队列但不是的题（？）。。。（复习一下）
1. Kth Element
215. Kth Largest Element in an Array (Medium)
在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
Input: [3,2,1,5,6,4] and k = 2 Output: 5
题目描述：找到倒数第 k 个的元素。
378题是第k小，这里是找第k大。。也可以用最大优先队列自动排序
方法一：堆排序
class Solution {
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> MaxPQ = new PriorityQueue<>(Collections.reverseOrder());
for(int num:nums){
MaxPQ.add(num);//先全给他加进去会自动排序 最大的在外面
}
for(int i = 1;i<k;i++){//把第k个前面的全出了
MaxPQ.remove();
}
return MaxPQ.remove();//第k个就找到了
}
}这里用最大优先队列，把比k位小的们都放在队列里，大的出掉了。
若改成用最小优先队列（最小堆），则应该是放入的是比k位大的们，则堆顶是最小的k位了。
看答案也太。。。Arrays.sort()用一下就出来。。。（JDK默认使用快速排序）
方法二：排序
public int findKthLargest(int[] nums, int k) {
int len = nums.length;
Arrays.sort(nums);
return nums[len - k];
}方法三：自己用代码实现快速排序的分治
借助 partition 操作定位到最终排定以后索引为 len - k 的那个元素（特别注意：随机化切分元素）
以下的描述基于 “快速排序” 算法知识的学习，如果忘记的朋友们可以翻一翻自己的《数据结构与算法》教材，复习一下，partition 过程、分治思想和 “快速排序” 算法的优化。
分析：我们在学习 “快速排序” 的时候，接触的第 1 个操作就是 partition（切分），简单介绍如下：
其中 partition 分区函数会任意选择一个元素作为 pivot（分区点），将数组中小于 pivot 的点都放置到其左边，将大于pivot的点都放置在其右边，最终 partition 函数返回 pivot 的下标 i
partition（切分）操作，使得：
对于某个索引 j，nums[j] 已经排定，即 nums[j] 经过 partition（切分）操作以后会放置在它 “最终应该放置的地方”；
nums[left] 到 nums[j - 1] 中的所有元素都不大于 nums[j]；
nums[j + 1] 到 nums[right] 中的所有元素都不小于 nums[j]。
partition（切分）操作总能排定一个元素，还能够知道这个元素它最终所在的位置，这样每经过一次 partition（切分）操作就能缩小搜索的范围，这样的思想叫做 “减而治之”（是 “分而治之” 思想的特例）。
切分过程可以不借助额外的数组空间，仅通过交换数组元素实现。
顺便回忆一下”快排“的实现
quick_sort(int[] arr, int low, int high) {
if (low >= high) return;
int i = partition(arr, low, high);//返回pivot的正确索引值
quick_sort(arr, low, i-1);
quick_sort(arr, i+1, high);
}该题答案：
class Solution {
//比较j与处理后的k（正序），分割知道j==k
public int findKthLargest(int[] nums, int k) {
k = nums.length - k;
int l = 0, h = nums.length - 1;
while (l < h) {
int j = partition(nums, l, h);//得到pivot的正确索引值
if (j == k) {
break;
} else if (j < k) {
l = j + 1;//选后半段
} else {
h = j - 1;//选前半段
}
}
return nums[k];
}
//在l~h范围内分割，找到位置为j的数 有点没看懂。。。
private int partition(int[] a, int l, int h) {
int i = l, j = h + 1;
while (true) {
while (a[++i] < a[l] && i < h) ;//这里是啥？？？？？交换还是just指针动？
while (a[--j] > a[l] && j > l) ;
if (i >= j) {
break;
}
swap(a, i, j);//???
}
swap(a, l, j);//????
return j;
}
//交换a[i]与a[j]
private void swap(int[] a, int i, int j) {
int t = a[i];
a[i] = a[j];
a[j] = t;
}
}没看懂。。。。？？？
桶排序
1. 出现频率最多的 k 个元素
Leetcode题号：347 难度：Medium
链接：https://leetcode-cn.com/problems/top-k-frequent-elements/description/
题目描述：
给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
写半天结果还是错的。。。就悟出了一个数组中加元素的道理
数组的初始化
你可以在声明数组的同时进行初始化（静态初始化），
也可以在声明以后进行初始化（动态初始化）。例如：
// 静态初始化
// 静态初始化的同时就为数组元素分配空间并赋值
int intArray[] = {1,2,3,4};
String stringArray[] = {"微学苑", "http://www.weixueyuan.net", "一切编程语言都是纸老虎"};
// 动态初始化
float floatArray[] = new float[3];
floatArray[0] = 1.0f;
floatArray[1] = 132.63f;
floatArray[2] = 100F;题目答案：
整道题思路可以分为3步：
1.将数组中的数按照 数字--出现频数 的格式存放在一个HashMap中。
2.将该HashMap中的内容放入一组桶中，其中，这组桶代表一个大ArrayList（第一次见这操作！）。这组桶的每一个元素都是一个桶（每个桶都是一个ArrayList），它的下标（索引）表示频数。每个桶都存放着对应该频数的数字。若同一频数的数字有多个，那么对应的桶中就会有多个数。
3.最后，从索引最大的桶开始，取出频数最大的k个数字即可。
上面是map 下面是桶，桶都是几到几一组的，比如这里是频率1到5的桶都有
注意其中用到的一些方法：
HashMap的getOrDefault（key，default）表示如果存在key对应的value，就返回该value，若不存在该key，就返回default位置的值。
ArrayList的addAll（）方法表示括号里的所有元素都添加到ArrayList中。
class Solution {
public List<Integer> topKFrequent(int[] nums, int k) {
//存放 数字-数字对应的频数
Map<Integer,Integer> f = new HashMap<>();
for (int num : nums) {
f.put(num, f.getOrDefault(num, 0) + 1);
}
//桶：桶的索引表示频数，每个索引位置放入对应频数的数字
List<Integer>[] buckets = new ArrayList[nums.length + 1];//因为下标设置成了从1开始？可是长度为啥加1？？
for (int key : f.keySet()) {
int frequency = f.get(key);//把map的计数值们都取出赋给了桶的索引值
if (buckets[frequency] == null) {
//因为可能存在频数相同的数字，因此每个索引位置都是一个数组
buckets[frequency] = new ArrayList<>();//桶的索引对应的值们存在arraylist里面
}
//根据桶的索引（频数），放入对应的数字（key）
buckets[frequency].add(key);//这个arraylist里面是map的key即输入数组元素值
}
List <Integer> topK = new ArrayList<>();
//从桶的最后一个元素开始遍历，往topK数组里面放频率最大的数，放满k个停止
for (int i = buckets.length - 1; i >= 0 && topK.size() < k; i--) {
//如果频率i没有对应的数，就跳过找下一个频率
if (buckets[i] == null) {
continue;
}
//当前频率的数的个数小于k，就将这些数全部放入topK
if (buckets[i].size() <= (k - topK.size())) {
topK.addAll(buckets[i]);
} else {
//topK还剩几个位子，就放几个数
topK.addAll(buckets[i].subList(0, k - topK.size()));
}
}
return topK;
}
}可是leetcode上返回的是int,需要转换一下，就是按索引遍历给数组一个一个加元素。
public int[] topKFrequent(int[] nums, int k) {
Map<Integer,Integer> map = new HashMap<>();
for(int num:nums){
map.put(num,map.getOrDefault(num,0)+1);
}
//桶排序
//将频率作为数组下标，对于出现频率不同的数字集合，存入对应的数组下标
List<Integer>[] list = new List[nums.length+1];//new一组桶List
for(int key : map.keySet()){
// 获取出现的次数作为下标
int i = map.get(key);
if(list[i] == null){
list[i] = new ArrayList();//每个索引对应的还是list
}
list[i].add(key);
}
// 倒序遍历数组获取出现顺序从大到小的排列
List<Integer> res = new ArrayList();
for(int i = list.length - 1;i >= 0 && res.size() < k;i--){
if(list[i] == null) continue;
res.addAll(list[i]);
}
int[] listt = new int[res.size()];
int idx=0;
for(int num:res){
listt[idx++]= num;
}
return listt;
}2. 按照字符出现次数对字符串排序
451. Sort Characters By Frequency (Medium)
给定一个字符串，请将字符串里的字符按照出现的频率降序排列。
示例 1:
输入:
"tree"
输出:
"eert"
解释:
‘e‘出现两次，‘r‘和‘t‘都只出现一次。
因此‘e‘必须出现在‘r‘和‘t‘之前。此外，"eetr"也是一个有效的答案。
class Solution {
public String frequencySort(String s) {
Map<Character,Integer> map = new HashMap<>();
//遍历String
for (char c : s.toCharArray()){
map.put(c, map.getOrDefault(c, 0) + 1);
}
List<Character>[] Bucket = new List[s.length()+1];//又是长度要加1 是个List们的数组们
for(char c:map.keySet()){
int f = map.get(c);//索引放入计数
if(Bucket[f] == null){
Bucket[f] = new ArrayList<>();
}
Bucket[f].add(c);
}
//从桶中索引最大的元素开始，依次取出字母放入可变字符串str中
StringBuilder str = new StringBuilder();
for (int i = Bucket.length - 1; i >= 0; i--) {
if (Bucket[i] == null) {
continue;
}
for (char c : Bucket[i]) {
for (int j = 0; j < i; j++) {
str.append(c);
}
}
}
return str.toString();
}
}荷兰国旗问题
荷兰国旗包含三种颜色：红、白、蓝。
有三种颜色的球，算法的目标是将这三种球按颜色顺序正确地排列。它其实是三向切分快速排序的一种变种，在三向切分快速排序中，每次切分都将数组分成三个区间：小于切分元素、等于切分元素、大于切分元素，而该算法是将数组分成三个区间：等于红色、等于白色、等于蓝色。
1. 按颜色进行排序
75. Sort Colors (Medium)
Input: [2,0,2,1,1,0] Output: [0,0,1,1,2,2]
给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
注意:
不能使用代码库中的排序函数来解决这道题。
示例:
输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]
答案：
1、len 是数组的长度；
2、变量 zero 是前两个子区间的分界点，一个是闭区间，另一个就必须是开区间；
3、变量 i 是循环变量，一般设置为开区间，表示 i 之前的元素是遍历过的；
4、two 是另一个分界线，我设计成闭区间。
public class Solution {
public void sortColors(int[] nums) {
int len = nums.length;
if (len < 2) {
return;
}
// all in [0, zero) = 0
// all in [zero, i) = 1
// all in [two, len - 1] = 2
// 循环终止条件是 i == two，那么循环可以继续的条件是 i < two
// 为了保证初始化的时候 [0, zero) 为空，设置 zero = 0，
// 所以下面遍历到 0 的时候，先交换，再加
int zero = 0;//占着最前面
// 为了保证初始化的时候 [two, len - 1] 为空，设置 two = len
// 所以下面遍历到 2 的时候，先减，再交换
int two = len-1;//占着最后面
int i = 0;
// 当 i == two 上面的三个子区间正好覆盖了全部数组
// 因此，循环可以继续的条件是 i <= two
while (i < =two) {//有点分治那意思，小的换前面去，大的换后面去
if (nums[i] == 0) {
swap(nums, i, zero);// i遇到0 把0换前面去。值交换，索引没有换，向右推1步
zero++;
i++;
} else if (nums[i] == 1) {
i++;//不管
} else {//i遇到2 把2换后面去 swap(nums, i, two); two--;
}
}
}
private void swap(int[] nums, int index1, int index2) {//传入的索引指针
int temp = nums[index1];
nums[index1] = nums[index2];
nums[index2] = temp;
}
}
作者：liweiwei1419
链接：https://leetcode-cn.com/problems/sort-colors/solution/kuai-su-pai-xu-partition-guo-cheng-she-ji-xun-huan/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。 
相关推荐
要知道时间复杂度只是描述一个增长趋势，复杂度为O的排序算法执行时间不一定比复杂度为O长，因为在计算O时省略了系数、常数、低阶。实际上，在对小规模数据进行排序时，n2的值实际比 knlogn+c还要小。