排序_牛客博客

冒泡排序

void maopao(int *a,int n){
    if(n==1)return;
    for(int i=1;i<n;i++)if(a[i]>a[i+1])swap(a[i],a[i+1]);
    maopao(a,n-1);
}

复杂度 $O(n^2)$

插入排序

每次将 $a[i]$ 插入到 $[1,i-1]$ 区间里。

图片说明

void insort(int *a,int n,int d){
    for(int i=d+1,j;i<=n;i++){
        if(a[i]>=a[i-d])continue;
        int r=a[i];
        for(j=i-d;r<a[j]&&j>0;j-=d)a[j+d]=a[j];
        a[j+d]=r;
    }
}

复杂度 $O(n^2)$

选择排序

每次选择 $[i+1,n]$ 区间的最小值和 $a[i]$ 交换。

图片说明

void selectsort(int *a,int n){
    for(int i=1;i<n;i++){
        int p=i;
        for(int j=i+1;j<=n;j++){
            if(a[p]>a[j])p=j;
        }
        swap(a[p],a[i]);
    }
}

复杂度 $O(n^2)$

希尔排序

希尔排序也称为“缩小增量排序”，基本原理是：首先将待排序的元素分为多个子序列，使得每个子序的元素个数相对较少，对各个子序分别进行直接插入排序，待整个待排序序列“基本有序后”，再对所有元素进行一次直接插入排序。

图片说明

void insort(int *a,int n,int d){
    for(int i=d+1,j;i<=n;i++){
        if(a[i]>=a[i-d])continue;
        int r=a[i];
        for(j=i-d;r<a[j]&&j>0;j-=d)a[j+d]=a[j];
        a[j+d]=r;
    }
}
void shellsort(int *a,int n){
    for(int d=n/2;d>=1;d>>=1)insort(a,n,d);
}

复杂度 $O(n \; log\; n)$

快速排序

对于一组给定的记录，通过一趟排序后，将原序列分为两部分，其中前部分的所有记录均比后部分的所有记录小，然后再依次对前后两部分的记录进行快速排序，递归该过程，直到序列中的所有记录均为有序为止。

图片说明

#include<bits/stdc++.h>
using namespace std;
#define me(a,x) memset(a,x,sizeof(a))
#define sc scanf
#define pr printf
#define IN freopen("in","r",stdin);
#define OUT freopen("out","w",stdout);
typedef long long ll;
typedef unsigned long long ull;
const int N=2e5+6;
const int mod=1e9+7;
int O(){putchar('\n');return 0;}template<typename T,typename... Ty>
int O(const T& a,const Ty&... b){cout<<a<<' ';return O(b...);}
void I(){}template<typename T,typename... Ty>void I(T& a,Ty&... b){cin>>a;I(b...);}
template<typename T>void db(T *bg,T *ed){while(bg!=ed)cout<<*bg++<<' ';pr("\n");}
inline ll mul_64(ll x,ll y,ll c){return (x*y-(ll)((long double)x/c*y)*c+c)%c;}
inline ll ksm(ll a,ll b,ll c){ll ans=1;for(;b;b>>=1,a=a*a%c)if(b&1)ans=ans*a%c;return ans;}
int a[N];
void medianOfThree(int m1,int m0,int m2){
    if(a[m1]<a[m0]){
        swap(a[m1],a[m0]);
    }
    if(a[m2]<a[m0]){
        swap(a[m2],a[m0]);
        if(a[m2]<a[m1]){
            swap(a[m2],a[m1]);
        }
    }
}
int getMid(int l,int r){
    int m=l+r>>1;
    if(r-l+1>40){
        int s=(r-l+1)>>3;
        medianOfThree(l,l+s,l+2*s);
        medianOfThree(m,m-s,m+s);
        medianOfThree(r,r-s,r-2*s);
    }
    medianOfThree(l,m,r);
    return l;
}
pair<int,int>doPiovt(int l,int r){
    int tmp=a[getMid(l,r)];
    for(int k=l;k<=r;){
        if(a[k]<tmp){
            swap(a[l],a[k]);
            k++,l++;
        }else if(a[k]>tmp){
            swap(a[r],a[k]);
            r--;
        }else{
            k++;
        }
    }
    return {l-1,r+1};
}
void msort(int l,int r){
    if(l>=r)return;
    if (r-l==1){
        if(a[r]<a[l]){
            swap(a[l],a[r]);
        }
        return;
    }
    pair<int,int>p=doPiovt(l,r);
    msort(l,p.first);
    msort(p.second,r);
}
int main(){
    int n;sc("%d",&n);
    for(int i=1;i<=n;i++){
        sc("%d",&a[i]);
    }
    msort(1,n);
    for(int i=1;i<=n;i++)pr("%d%c",a[i]," \n"[i==n]);
}

复杂度 $O(n\; log \;n)$

归并排序

利用递归与分治技术将数据序列划分为越来越小的半子表，再对半子表排序，最后再用递归步骤将排好序的半子表合并成为越来越大的有序序列。
图片说明

void merge(int *a,int l,int mid,int r){
    if(r-l==1){
        if(a[l]>a[r])std::swap(a[l],a[r]);
        return;
    }
    int* b=new int[r-l+1];
    int p=0,i=l,j=mid+1;
    while(p<r-l+1){
        if(i<=mid&&j>r)b[p++]=a[i++];
        else if(i>mid&&j<=r)b[p++]=a[j++];
        else{
            if(a[i]<a[j])b[p++]=a[i++];
            else b[p++]=a[j++];
        }
    }
    for(i=l,p=0;i<=r;i++,p++)a[i]=b[p];
    delete []b;
}
void sort_(int *a,int l,int r){
    if(l>=r)return ;
    int mid=l+r>>1;
    sort_(a,l,mid);
    sort_(a,mid+1,r);
    merge(a,l,mid,r);
}

复杂度 $O(n \; log\; n)$

堆排序

图片说明

template<typename T,size_t _n>
struct hep{
    int n;T *q;
    hep(){n=0;q=new int[_n];}
    ~hep(){delete []q;}
    void up(int i){ //上浮
        for(;i>1;i>>=1)
        if(q[i]<q[i>>1])swap(q[i],q[i>>1]);
    }
    void down(int i){ //下浮
        while((i<<1)<=n){
            int k=i<<1;
            if(k<n&&q[k+1]<q[k])++k;
            if(q[i]>q[k])swap(q[i],q[k]),i=k;
            else return;
        }
    }
    void push(const T& x){
        q[++n]=x;up(n);
    }
    void pop(){
        swap(q[1],q[n--]);
        down(1);
    }
    T top(){return q[1];}
    bool empty(){return n==0;}
};

or
int n,a[N],m;
void down(int pos){
    while((pos<<1)<=m){
        int k=pos<<1;
        if(k<m&&a[k]>a[k+1])k++;
        if(a[pos]>a[k]){
            swap(a[k],a[pos]);
            pos=k;
        }else break;
    }
} 
void pop(){
    swap(a[1],a[m]);
    m--;
    down(1);
}
int main(){
    srand(time(0));
    n=rand()%100+1;
    m=n;
    for(int i=1;i<=n;i++)a[i]=i;
    int t=10;
    while(t--)
    for(int i=n-1;i>=0;i--){
        int id=rand()%(i+1);
        swap(a[i+1],a[id+1]);
    }
    db(a+1,a+1+n);
    for(int i=n/2;i>=1;i--)down(i); //O(n);建堆。
    for(int i=1;i<n;i++){
        pr("%d ",a[1]);
        pop();
    }
    pr("%d\n",a[1]);
    db(a+1,a+1+n);
}

复杂度 $(n\; log\; n)$

$O(n)$ 建堆复杂度：
每次上升一层 $h$ ，最多向下走 $O(h)$ 的时间， $h$ 层的节点最多有 $\frac{n}{2^{h+1}}$ 个，
所以总共 $\sum_{h=0}^{\log n}O(h)\cdot \frac{n}{2^{h+1}}=O(n\sum_{h=0}^{inf}\frac{n}{2^h})=O(2n)$

基数排序

(1)分配，先从个位开始，根据位值(0-9)分别放到0~9号桶中（比如53,个位为3，则放入3号桶中）

(2)收集，再将放置在0~9号桶中的数据按顺序放到数组中

图片说明

void _sort(int *a,int d,int n){
    int b[10]={0};
    int *t=new int[n+1];
    for(int i=1;i<=n;i++)b[(a[i]/d)%10]++;
    for(int i=1;i<10;i++)b[i]+=b[i-1];
    for(int i=n;i>=1;i--){
        int k=(a[i]/d)%10;
        t[b[k]--]=a[i];
    }
    for(int i=1;i<=n;i++)a[i]=t[i];
    delete []t;
}
void rad(int *a,int n){
    int p=1,d=1;
    for(int i=1;i<=n;i++)if(a[p]<a[i])p=i;
    p=a[p];
    while(p){
        p/=10;_sort(a,d,n);
        d*=10;
    }
}