排序算法，一般都可以使用std：：sort（）来快速排序。
这里介绍一些相关的算法，巩固记忆。
快速排序
跟二分查找有一丢丢像。
首先选择一个基准元素，一般就直接选择第一个。然后两个指针，一个指向第一个，一个指向最后一个。第一个现在是空，就从最后一个开始，跟基准元素做判断，小于基准元素的就放到第一个位置，然后第一指针往后移。按这种顺序直到两个指针相遇，相遇的位置放入基准元素。然后从基准元素劈开两半，再按相同方法排序。
void quicksort(vector<int> nums,int l,int r){if(l+1>=r)return;int first=l,last=r-1;int key=nums[first];while(first<=last){while(first<last&&nums[last]>=key)last--;nums[first]=nums[last];while(first<last&&nums[first]<=key)first++;nums[last]=nums[first];}nums[first]=key;quicksort(nums,l,first);quicksort(nums,first+1,r); }
归并算法
归并算法是一种分治算法，先分再治。比如说8个数字。先分成4个4个，然后4个内部再继续分，分成2个2个。2个排好序后合并，4个排好序后再合并。
void merge_sort(vector<int> &nums,int l,int r,vector<int>& temp){if(l+1>=r)return ;int m=(l+r)/2;merge_sort(nums,l,m,temp);merge_sort(nums,m+1,r,temp);int a=l,b=m,i=l;while(a<m||b<r){if(nums[a]<nums[b])nums[i++]=nums[a++];elsenums[i++]=nums[b++];}for(i=l;i<r;i++)nums[i]=temp[i]; }
插入排序
首先是一个数，本来就有序。接着两个数进行排序。接着三个数。
所谓插入，比如说八个数进行排序，其实前七个已经有序，这个时候只需要把第八个插入到前七个数的合适位置即可。怎么插入，就从后往前，一个一个比较，如果小于就往前移。
void insert_sort(vector<int>& nums,int n){int i,j;for(i=0;i<n;i++){for(j=i;j>0;j--){if(nums[j]>nums[j-1])swap(nums[j],nums[j-1]);}} }
冒泡排序
相邻两个数比较，大的往后移，每一轮最大的数将会移到最后。
可以进行一个优化，可能出现一种情况，从第二轮过后，其实数组已经是有序的了，但是按照算法步骤来走的话，即使已经排好序了，但仍是会进行后边的比较，知道全部比较完成
因此，我们可以对代码进行优化，如果发现在某趟排序中，没有发生一次交换， 可以提前结束冒泡排序。
解决方式：可以通过一个标志位来进行判断
void bubble_sort(vector<int>& nums,int n){int flag=false;int i,j;for(i=1;i<n;i++){flag=false;for(j=1;j<n-i+1;j++){if(nums[j]<nums[j-1]){swap(nums[j],nums[j-1]);flag=true;} }if(flag==false)return ;} }
选择排序
选择最小的数跟第一个数交换，按照同样的方法对后面的n-1个进行排序。
void select_sort(vector<int>& nums,int n){int i,j;for(i=0;i<n;i++){int m=i;for(j=i+1;j<n;j++){if(nums[j]<nums[m]){m=j;}}swap(nums[i],nums[m]);} }
215.数组中的第K个元素
215. 数组中的第K个最大元素
给定整数数组
nums和整数k，请返回数组中第k个最大的元素。请注意，你需要找的是数组排序后的第
k个最大的元素，而不是第k个不同的元素。你必须设计并实现时间复杂度为
O(n)的算法解决此问题。示例 1:
输入:[3,2,1,5,6,4], k = 2输出: 5示例 2:
输入:[3,2,3,1,2,4,5,5,6], k = 4输出: 4提示：
1 <= k <= nums.length <=<= nums[i] <=
题解
可以利用快速排序的思想来解决这个问题。
选择一个数，然后将大于它的数字往后移，小于的往前移。如果这个刚好是第k位，直接返回。如果不是，大于k，则对前面做相同的排序，如果不是就对后面做相似的排序。这里的k指的是第k大，因此从小到大排就是第n-k位。
class Solution {
public:int quickselect(vector<int> &nums,int l,int r,int k){if(l==r)return nums[k];int p=nums[l],i=l-1,j=r+1;while(i<j){do i++; while (nums[i] < p);do j--; while (nums[j] > p);if(i<j)swap(nums[i],nums[j]);}if(k<=j) return quickselect(nums,l,j,k);else return quickselect(nums,j+1,r,k);}int findKthLargest(vector<int> &nums, int k) {int n=nums.size();return quickselect(nums,0,n-1,n-k);}
};347.前k个高频元素
347. 前 K 个高频元素
题目
给你一个整数数组
nums和一个整数k，请你返回其中出现频率前k高的元素。你可以按 任意顺序 返回答案。示例 1:
输入: nums = [1,1,1,2,2,3], k = 2 输出: [1,2]示例 2:
输入: nums = [1], k = 1 输出: [1]提示：
1 <= nums.length <=k的取值范围是[1, 数组中不相同的元素的个数]- 题目数据保证答案唯一，换句话说，数组中前
k个高频元素的集合是唯一的
题解
可以使用桶排序，使用STL库中的unordered_map，提供了一种基于哈希表的键值对容器。
可以对每一个数字出现的次数进行计算并且存储。
unordered_map<int,int> m;for(int num:nums) m[num]++;接着进行排序，然后再定义一个新的数组用来存储要返回的数组。
class Solution { public:vector<int> topKFrequent(vector<int>& nums, int k) {unordered_map<int,int> m;for(int num:nums) m[num]++;vector<pair<int,int>> s;for(auto t:m)s.push_back({t.second,t.first});sort(s.begin(),s.end());vector<int> ans;int t=s.size()-1;while(k--){ans.push_back(s[t--].second);}return ans;} };排序这里也有一个库可以使用。
<priority_queue>是标准模板库（STL）的一部分，用于实现优先队列。优先队列是一种特殊的队列，它允许我们快速访问队列中具有最高（或最低）优先级的元素。
class Solution { public:vector<int> topKFrequent(vector<int>& nums, int k) {unordered_map<int,int> m;for(int num:nums) m[num]++;priority_queue<pair<int,int>> s;for(auto i:m) s.emplace(i.second,i.first);vector<int> ans;while(k--){ans.push_back(s.top().second);s.pop();}return ans;} };不得不说如果熟悉使用STL库，真的省事很多。
-熔断)
