排序算法，一般都可以使用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++]; else nums[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库，真的省事很多。
