sort

bubble_sort:

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

select_sort:

void select_sort(int a[],int n)
{
    for(int i=1;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]);
    }
}

insert_sort:

void insert_sort(int a[],int n)
{
    for(int i=2; i<=n; i++)
    {
        int t=a[i],j;
        for(j=i; j>=2&&a[j-1]>t; j--)
            a[j]=a[j-1];
        a[j]=t;
    }
}

merge_sort:

int t[100005];
void merge_sort(int st,int ed,int a[],int t[])
{
    int mid=(st+ed)/2;
    if(st!=mid)merge_sort(st,mid,a,t);
    if(mid+1!=ed)merge_sort(mid+1,ed,a,t);
    int x=st,y=mid+1,k=st;
    while(x<=mid&&y<=ed)
        if(a[x]<a[y])t[k++]=a[x++];
        else t[k++]=a[y++];
    while(x<=mid)t[k++]=a[x++];
    while(y<=ed)t[k++]=a[y++];
    for(int i=st; i<=ed; i++)
        a[i]=t[i];
}

quick_sort:

void quick_sort(int a[],int l,int r)
{
    if(l>=r)return;
    int x=rand()%(r-l+1)+l;
    int mid=(l+r)>>1;
    swap(a[x],a[r]);
    int i=l,j=r-1;
    while(1)
    {
        while(a[i]<a[r])i++;
        while(a[j]>a[r])j--;
        if(j<i)break;
        swap(a[i++],a[j--]);
    }
    swap(a[i],a[r]);
    quick_sort(a,l,i-1);
    quick_sort(a,i,r);
}