內建排序函式的使用

範例 1

int arr[100010];
要排前\(n\)項
sort(arr,arr+n);

範例 1

int arr[100010];
要由大到小排前\(n\)項
sort(arr,arr+n,greater<int>());

範例一

int n;
int arr[100010];
 
bool cmp(int a,int b){
    return a>b;
}
 
sort(arr,arr+n,cmp);

很慢，不建議使用

範例二

Lambda function

int n;
int arr[100010];
 
sort(arr,arr+n,[](int a,int b){
    return a>b;
});

很快，推薦使用

範例三

函式物件

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

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;
});

• 一樣是struct排序
• 也一樣超快Don't use cmp function
• 以後再說

code

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);

• vector
• string
• deque

用stl.begin(),stl.end()代替arr,arr+n

code

vector<int> v(n);
sort(v.begin(),v.end());

code

#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);
}

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();
}