# 內建排序函式的使用 --- - 預設為由小到大排序 - `sort(beginPtr,endPtr);` - `sort(beginPtr,endPtr,cmp);` - `stable_sort(beginPtr,endPtr);` - `stable_sort(beginPtr,endPtr,cmp);` ---- ### 範例 1 `int arr[100010];` 要排前$n$項 `sort(arr,arr+n);` ---- ### 範例 1 `int arr[100010];` 要由大到小排前$n$項 `sort(arr,arr+n,greater<int>());` --- ## 比較函式的使用 ---- ### 範例一 ```cpp= int n; int arr[100010]; bool cmp(int a,int b){ return a>b; } sort(arr,arr+n,cmp); ``` 很慢，不建議使用 ---- ### 範例二 #### Lambda function ```cpp= int n; int arr[100010]; sort(arr,arr+n,[](int a,int b){ return a>b; }); ``` 很快，推薦使用 ---- ### 範例三 #### 函式物件 ```cpp= struct cmp{ bool operator() (const int &a,const int &b) const{ return a>b; } }; int n; int arr[100010]; sort(arr,arr+n,cmp); ``` 很快 ---- ### 其他運用 - `struct`排序 - 以後會教 ---- code ```cpp= struct Pt{ int x,y; }; sort(arr,arr+n,[](Pt a,Pt b){ if(a.y!=b.y) return a.y<b.y; return a.x<b.x; }); ``` --- ### Overwrite Operator ---- - 一樣是struct排序 - 也一樣超快~~Don't use cmp function~~ - 以後再說 ---- code ```cpp= struct Pt{ int x,y; friend bool operator<(Pt a,Pt b){ return a.x+a.y<b.x+b.y; } }; sort(arr,arr+n); ``` --- ### 對STL排序 ---- - vector - string - deque ---- 用`stl.begin(),stl.end()`代替`arr,arr+n` ---- code ```cpp= vector<int> v(n); sort(v.begin(),v.end()); ``` --- 補充 : MergeSort ---- code ```cpp= #include<bits/stdc++.h> using namespace std; using ll=long long; ll arr[1000010]; int n=10; void merge_sort(int l,int r){// [l,r) if(l+1>=r) return; int mid=(l+r)/2; merge_sort(l,mid); merge_sort(mid,r); merge( arr+l,arr+mid, arr+mid,arr+r, arr+l ); for(int i=0;i<n;++i){ cout<<arr[i]<<" "; } cout<<"\n"; } int main(){ ios::sync_with_stdio(0);cin.tie(0); for(int i=0;i<n;++i){ cin>>arr[i]; } merge_sort(0,n); } ``` --- 補充：heap sort ---- ```cpp= int arr[100010]; priority_queue<int,vector<int>,greater<int>> pq; for(int i=0;i<n;++i){ pq.push(arr[i]); } for(int i=0;i<n;++i){ arr[i]=pq.top(); pq.pop(); } ```