排序

均按非降序排序

一、计数排序

int findmax(int* arr,int n)
{
    int max=arr[0];
    for(int i=1;i<n;++i)
        if(arr[i]>max) max=arr[i];
    return max+1;
}
void counting_sort(int* arr,int n)
{
    int len=findmax(arr,n);
    int *bkt=new int[len];
    memset(bkt,0,len*sizeof(int));
    for(int i=0;i<n;++i)
        ++bkt[arr[i]];
    int k=0;
    for(int i=0;i<len;++i) 
        while(bkt[i]--)
            arr[k++]=i;
    delete []bkt;
}

二、选择排序

void selection_sort(int* arr,int n)
{
    for(int i=0;i<n-1;++i)
        for(int j=i+1;j<n;++j)
            if(arr[j]<arr[i])
                std::swap(arr[i],arr[j]);
}

三、冒泡排序

void bubble_sort(int* arr,int n)
{
    for(int i=0;i<n-1;++i)
        for(int j=0;j<n-i-1;++j)
            if(arr[j]>arr[j+1])
                std::swap(arr[j],arr[j+1]);
}

四、插入排序

void insertion_sort(int* arr,int n)
{
    for(int i=1;i<n;++i){
        int cur=arr[i],j;
        for(j=i-1;j>=0;--j)
            if(arr[j]>cur) arr[j+1]=arr[j];
            else break;
        arr[j+1]=cur;
    }           
}

五、希尔排序

void insert(int* arr,int gap,int i)
{
    int cur=arr[i],j;
    for(j=i-gap;j>=0&&arr[j]>cur;j-=gap)
        arr[j+gap]=arr[j];
    arr[j+gap]=cur;
}
void shell_sort(int* arr,int n)
{
    int gap;
    for(gap=n/2;gap;gap/=2){
        for(int i=gap;i<n;++i)
            insert(arr,gap,i);
    }
}

六、快速排序

//递归
int ar[];
void quick_sort(int left,int right)
{
    int i,j;
    if(left>=right) return;
    int temp=ar[left];
    i=left; j=right;
    while(i!=j){
        while(ar[j]>=temp&&i<j) --j;
        while(ar[i]<=temp&&i<j) ++i;
        if(i<j) std::swap(ar[i],ar[j]);
    }
    ar[left]=ar[i];
    ar[i]=temp;
    quick_sort(left,i-1);
    quick_sort(i+1,right);
}

//非递归
int division(int left,int right,int* arr)
{
    int i=left,j=right;
    int temp=arr[left];
    while(i!=j)
    {
        while(arr[j]>=temp&&i<j) --j;
        while(arr[i]<=temp&&i<j) ++i;
        if(i<j) std::swap(arr[i],arr[j]);
    }
    arr[left]=arr[i];
    arr[i]=temp;
    return i;
}
void quick_sort(int* arr,int n)
{
    int left=0,right=n-1;
    std::stack<int> st;
    st.push(left);
    st.push(right);
    while(!st.empty())
    {
        right=st.top();
        st.pop();
        left=st.top();
        st.pop();
        int index=division(left,right,arr);
        if(index-left>1)
        {
            st.push(left);
            st.push(index-1);
        }
        if(right-index>1)
        {
            st.push(index+1);
            st.push(right);
        }
    }
}

七、桶排序

void bucket_sort(int* arr,int n)
{
    int min=arr[0],max=arr[0];
    for(int i=1;i<n;++i){
        if(arr[i]>max) max=arr[i];
        if(arr[i]<min) min=arr[i];
    }
    std::vector<int>* bucket=new std::vector<int>[n];
    for(int i=0;i<n;++i){
        int tmp=(arr[i]-min)*(n-1)/(max-min);
        bucket[tmp].push_back(arr[i]);
    }
    for(int i=0;i<n;++i){
        if(bucket[i].size()>1) sort(bucket[i].begin(),bucket[i].end());
    }
    int k=0;
    for(int i=0;i<n;++i)
        for(int t2:bucket[i])
            arr[k++]=t2;
    delete []bucket;
}

八、基数排序

int tenx(int n)
{
    if(!n) return 1;
    int ret=1;
    for(int i=0;i<n;++i)
        ret*=10;
    return ret;
}
void radix_sort(int* arr,int n)
{
    int max=arr[0];
    for(int i=1;i<n;++i)
        if(arr[i]>max) max=arr[i];
    int num=1;
    while(max/=10) ++num;
    std::vector<int>* bucket=new std::vector<int>[10];
    for(int i=0;i<num;++i)
    {
        for(int j=0;j<n;++j)
        {
            int tmp=arr[j]/tenx(i)%10;
            bucket[tmp].push_back(arr[j]);
        }
        int k=0;
        for(int i=0;i<10;++i)
        {
            for(int t:bucket[i]) arr[k++]=t;
            bucket[i].clear();
        }
    }
    delete []bucket;
}

九、归并排序

//非递归
void merge(int* arr,int* tmp,int left,int mid,int right)
{
    int left1=left,right1=mid;
    int left2=mid+1,right2=right;
    int k=left;
    while(left1<=right1 && left2<=right2)
    {
        if(arr[left1]<arr[left2]) tmp[k++]=arr[left1++];
        else tmp[k++]=arr[left2++];
    }
    while(left1<=right1) tmp[k++]=arr[left1++];
    while(left2<=right2) tmp[k++]=arr[left2++];
    for(int i=left;i<=right;++i) arr[i]=tmp[i];
}
void merge_sort(int* arr,int n)
{
    int* tmp=new int[n];
    int len = 1;
    while(len<n)
    {
        for(int i=0;i+len<=n;i+=(len<<1))
        {
            int left=i;
            int mid=i+len-1;
            int right=i+(len<<1)-1;
            if(right>n-1) right=n-1;
            merge(arr,tmp,left,mid,right);
        }
        len<<=1;
    }
    delete []tmp;
}

//递归
void merge_sort(int* arr,const int n,int left,int right)
{
    if(left>=right) return;
    int *temp=new int[n];
    int mid=(left+right)>>1;
    int left1=left,right1=mid;
    int left2=mid+1,right2=right;
    merge_sort(arr,n,left1,right1);
    merge_sort(arr,n,left2,right2);
    int k=left;
    while(left1<=right1&&left2<=right2){
        if(arr[left1]<=arr[left2]) temp[k++]=arr[left1++];
        else temp[k++]=arr[left2++];
    }
    while(left1<=right1) temp[k++]=arr[left1++];
    while(left2<=right2) temp[k++]=arr[left2++];
    for(int i=left;i<=right;++i) arr[i]=temp[i];
    delete []temp;
}

十、堆排序

//最小堆
void siftdown(int* arr,int n,int i)
{
    int t;
    while((i<<1)+1<n)
    {
        if(arr[i]>arr[(i<<1)+1]) t=((i<<1)+1); 
        else t=i;
        if((i<<1)+2<n)
            if(arr[(i<<1)+2]<arr[t]) 
                t=(i<<1)+2;
        if(t!=i)
        {
            std::swap(arr[i],arr[t]);
            i=t;
        }
        else break;
    }
}
void creat_heap(int* arr,int n)
{
    for(int i=((n-1)>>1);i>=0;--i)
        siftdown(arr,n,i);
}
int select_min(int* arr,int n)
{
    static int cnt=n;
    int t;
    t=arr[0];
    arr[0]=arr[cnt-1];
    --cnt;
    siftdown(arr,cnt,0);
    return t;
}
void heap_sort(int* arr,int n)
{
    int* a=new int[n];
    for(int i=0;i<n;++i) a[i]=arr[i];
    creat_heap(a,n);
    for(int i=0;i<n;++i) arr[i]=select_min(a,n);
    delete []a;
}

//最大堆
void siftdown(int* arr,int n,int i)
{
    int t;
    while((i<<1)+1<n)
    {
        if(arr[i]<arr[(i<<1)+1]) t=((i<<1)+1); 
        else t=i;
        if((i<<1)+2<n)
            if(arr[(i<<1)+2]>arr[t]) 
                t=(i<<1)+2;
        if(t!=i)
        {
            std::swap(arr[i],arr[t]);
            i=t;
        }
        else break;
    }
}
void creat_heap(int* arr,int n)
{
    for(int i=((n-1)>>1);i>=0;--i)
        siftdown(arr,n,i);
}
void heap_sort(int* arr,int n)
{
    creat_heap(arr,n);
    while(n>0)
    {
        std::swap(arr[0],arr[n-1]);
        --n;
        siftdown(arr,n,0);
    }
}