全平台肘击桑境阳，支持者复制红字挂主页 全平台肘击桑境阳，支持者复制红字挂主页 全平台肘击桑境阳，支持者复制红字挂主页 洛谷账号：chengyuhan13579

快速排序

#include<bits/stdc++.h>
using namespace std;
vector<long long> v;
int i,j,temp;
void quicksort(int l,int r){
    if(l>r){
        return;
    }
    temp=v[l];
    i=l;
    j=r;
    while(i!=j){
        while(v[j]>=temp&&i<j){
            j--;
        }
        while(v[i]<=temp&&i<j){
            i++;
        }
        if(i!=j){
            swap(v[i],v[j]);
        }
    }
    swap(v[l],v[j]);
    quicksort(l,j-1);
    quicksort(i+1,r);
}
int main(){
    int n,x,cnt;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>x;
        v.push_back(x);
    }
    quicksort(0,n-1);
    for(int i=0;i<n;i++){
        cout<<v[i]<<' ';
    }
    return 0;
}

归并排序

#include<bits/stdc++.h>
using namespace std;
vector<int> s1,s2;
void marge(int l,int m,int r){
     s2.clear();
     int i=l,j=m+1;
     while(i<=m&&j<=r){
         if(s1[i]<s1[j]){
            s2.push_back(s1[i++]);
         }else{
            s2.push_back(s1[j++]);
         }
     }
     while(i<=m){
         s2.push_back(s1[i++]);
     }
     while(j<=r){
         s2.push_back(s1[j++]);
     }
     for(i=l;i<=r;i++){
        s1[i]=s2[i-l];
     }
}
void margesort(int a,int b){
     if(a==b){
       return;
     }
     int m=(a+b)/2;
     margesort(a,m);
     margesort(m+1,b);
     marge(a,m,b);
}
int main(){
    int n,x;
    cin>>n;
    for(int i=1;i<=n;i++){
       cin>>x;
       s1.push_back(x);
    }
    margesort(0,n-1);
    for(int i=0;i<n;i++){
       cout<<s1[i];
    }
    return 0;
}

选择排序

#include<bits/stdc++.h>
using namespace std;
void fun(int a[],int n){
     for(int i=0;i<n;i++){
        int minn=i;
        for(int j=i+1;j<n;j++){
          if(a[j]<a[minn]){
            minn=j;
          }
        }
     swap(a[i],a[minn]);
     }
}
int main(){
    int n,a[305];
    cin>>n;
    for(int i=0;i<n;i++){
      cin>>a[i];
    } 
    fun(a,n);
    for(int i=0;i<n;i++){
      cout<<a[i];
    }
    return 0;
}

插入排序

#include<bits/stdc++.h>
using namespace std;
void insertsort(int a[],int n){
     int x;
     for(int i=1;i<n;i++){
        x=a[i];
        int j=0;
        for(j=i-1;j>=0;j--){
           if(a[j]>x){
             a[j+1]=a[j];
           }else{
             a[j+1]=x;
           }
        }
        if(j<0){
          a[0]=x;
        }
    }
}
int main(){
   int n,v[1005];
   cin>>n;
   for(int i=0;i<n;i++){
      cin>>v[i];
   }
   insertsort(v,n);
   for(int i=0;i<n;i++){
      cout<<v[i];
   }
   return 0;
}

二分查找

#include<bits/stdc++.h>
using namespace std;
int n,x,h;
vector<int> a;
int fun(){
    int l=1,r=n,v;
    while(l<r){
        v=(l+r)/2;
        if(a[v]>=x){
            r=v;
        }else{
            l=v+1;
        }
    }
    if(x==a[l]){
        return l;
    }else{
        return -1;
    }
}
int main(){
   cin>>n;
   for(int i=1;i<=n;i++){
      scanf("%d",&h);
      a.push_back(h);
   }
   cin>>x;
   printf("%d",fun()+1);
}

堆排序

#include<bits/stdc++.h>
using namespace std;
const int N=1e+6;
int n,a[N];
void heapify(int n,int i){
    int largest=i,lson=2*i,rson=2*i+1;
    if(a[largest]<a[lson]&&lson<=n){
        largest=lson;
    }
    if(a[largest]<a[rson]&&rson<=n){
        largest=rson;
    }
    if(a[i]!=a[largest]){
        swap(a[i],a[largest]);
        heapify(n,largest);
    }
}
void heapsort(){
    for(int i=n/2;i>=1;i--){
        heapify(n,i);
    }
    for(int i=n;i>1;i--){
        swap(a[1],a[i]);
        heapify(i-1,1);
    }
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    heapsort();
    for(int i=1;i<=n;i++){
        cout<<a[i];
    }
}

以大根堆为例： 1、首先先找到最后一个非叶子结点，假设n个元素。 那么⌊n/2」 2、把完全二叉树自底向上修改成大根堆的形式，每修改一个数据，数组里面对应的数据需要随之变化。 3、当变成大根堆的时候，祖宗结点(a[1])一定是最大的，那么只需要和a[n]交换。总共有n个数，那么只需要n-1次就可以排完

基数排序

#include<bits/stdc++.h>
using namespace std;
const int N=1e+5;
int a[N],t[N];
int buchet[10];
void redixSort(int n){
    int max_val=*(max_element(a,a+n));
    int base=1;
    while(max_val/base>0){
        memset(buchet,0,sizeof(buchet));
        for(int i=0;i<n;i++){
            buchet[a[i]/base%10]++;
        }
        for(int i=1;i<10;i++){
            buchet[i]=buchet[i]+buchet[i-1];
        }
        for(int i=n-1;i>=0;i--){
            int v=a[i]/base%10;
            t[--buchet[v]]=a[i];
        }
        for(int i=0;i<n;i++){
            a[i]=t[i];
        }
        base*=10;
    }
}
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        scanf("%d",a+i);
    }
    redixSort(n);
    for(int i=0;i<n;i++){
        printf("%d",a[i]);
    }
    return 0;
}

高精度减法

#include<bits/stdc++.h>
using namespace std;
const int N=1e+6;
string a1,b1;
bool flag=false;
int a[N],b[N],c[N];
bool panduan(string s1,string s2){
    if(s1.size()!=s2.size()) return s1.size()<s2.size();
    else return s1<s2;
}
int main(){
    cin>>a1>>b1;
    if(panduan(a1,b1)){
        cout<<'-';
        swap(a1,b1);
    }
    for(int i=a1.size()-1,j=0;i>=0;i--,j++){
        a[j]=a1[i]-'0';
    }
    for(int i=b1.size()-1,j=0;i>=0;i--,j++){
        b[j]=b1[i]-'0';
    }
    int len=max(a1.size(),b1.size());
    for(int i=0;i<len;i++){
        c[i]+=a[i]-b[i];
        if(c[i]<0){
            c[i]+=10;
            c[i+1]--;
        }
    }
    for(int i=len-1;i>=0;i--){
        if(c[i]!=0){
            flag=true;
        }
        if(flag){
            cout<<c[i];
        }
    }
    if(flag==false){
        cout<<0;
    }
    return 0;
}

高精度加法

#include<bits/stdc++.h>
using namespace std;
int main(){
    string a1,b1;
    bool flag=0;
    int a[1000]={0},b[1000]{0},c[1000]={0};
    cin>>a1>>b1;
    for(int i=a1.size()-1,j=0;i>=0;i--,j++){
        a[j]=a1[i]-'0';
    }
    for(int i=b1.size()-1,j=0;i>=0;i--,j++){
        b[j]=b1[i]-'0';
    }
    for(int i=0;i<a1.size()||i<b1.size();i++){
        c[i]=a[i]+b[i];
    }
    for(int i=0;i<a1.size()||i<b1.size();i++){
        if(c[i]>=10){
            c[i]-=10;
            c[i+1]++;
        }
    }
    for(int i=max(a1.size()+1,b1.size()+1);i>=0;i--){
        if(c[i]!=0){
            flag=1;
        }
        if(flag){
            cout<<c[i];
        }
    }
}

哈希算法

#include<bits/stdc++.h>
using namespace std;
const int N=1e+5;
int hash1[N],HMAX,cnt[N],b[N];
void hashinit(int x){
    for(int i=1;i<=x;i++){
        hash1[i]=-1;
    }
}
void hashinsert(int x){
    int y=x%HMAX;
    while(1){
        if(hash1[y]==-1){
            hash1[y]=x;
            cnt[y]=1;
            return;
        }else if(hash1[y]==x){
            cnt[y]++;
            return;
        }
        if(++y>HMAX){
            y=1;
        }
    }
}
int hashget(int x){
    int y=x%HMAX;
    while(1){
        if(hash1[y]==-1){
            return 0;
        }else if(hash1[y]==x){
            return cnt[y];
        }
        if(++y>HMAX){
            y=1;
        }
    }
}
int main(){
    int x;
    cin>>HMAX;
    hashinit(HMAX);
    for(int i=1;i<=HMAX;i++){
        cin>>x;
        hashinsert(x);
    }
    //根据题目变化
    return 0;
}

Dijkstra朴素算法

#include<bits/stdc++.h>
using namespace std;
const int MAXN=100;
int graph[MAXN][MAXN];
void initEdegs(int n){
    for(int u=0;u<n;u++){
        for(int v=0;v<n;v++){
            graph[u][v]=INT_MAX;
        }
    }
}
void addEdge(int u,int v,int w){
    graph[u][v]=min(graph[u][v],w);
}
void DijkstraInit(int n,int s,bool visited[],int dist[]){
    for(int i=0;i<n;i++){
        visited[i]=false;
        dist[i]=INT_MAX;
    }
    dist[s]=0;
}
int DijkstraFindMin(int n,bool visited[],int dist[]){
    int u=-1;
    for(int i=0;i<n;i++){
        if(visited[i]) continue;
        if(u==-1||dist[i]<dist[u]){
            u=i;
        }
    }
    return u;
}
void DijkstraUpdate(int n,int u,bool visited[],int dist[]){
    visited[u]=true;
    for(int i=0;i<n;i++){
        if(visited[i]) continue;
        if(graph[u][i]!=INT_MAX){
            dist[i]=min(dist[i],dist[u]+graph[u][i]);
        }
    }
}
void Dijkstra(int n,int s,int dist[]){
    bool visited[MAXN];
    DijkstraInit(n,s,visited,dist);
    while(true){
        int u=DijkstraFindMin(n,visited,dist);
        if(u==-1) return;
        DijkstraUpdate(n,u,visited,dist);
    }
}
int main(){
    int n,m,s;
    cin>>n>>m>>s;
    initEdegs(n);
    for(int i=0;i<m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        addEdge(u,v,w);
    }
    int dist[MAXN];
    Dijkstra(n,s,dist);
    for(int i=0;i<n;i++){
        if(dist[i]==INT_MAX){
            cout<<"INF ";
        }else{
            cout<<dist[i]<<" ";
        }
    }
    cout<<endl;
    return 0;
}

希尔排序

#include <bits/stdc++.h>
using namespace std;
const long long N=1e+5;
int a[N];
void shell_sort(int n){
    int gap=n/2;
    while(gap>0){
        for(int i=gap;i<n;i++){
            int temp=a[i];
            int j=i;
            while(j>=gap&&temp<a[j-gap]){
                a[j]=a[j-gap];
                j-=gap;
            }
            a[j]=temp;
        }
        gap/=2;
    }
}
int main(){
    int n;
    cin>>n;
    for (int i = 0; i < n; i++){
        cin>>a[i];
    }
    shell_sort(n);
    for (int i=0;i<n;i++){
        cout<<a[i]<<' ';
    }
    return 0;
}