排序算法，一般都可以使用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庫，真的省事很多。
