#include<iostream>
#include<cstdlib>
#include<ctime>
using namespace std;
const int len = 20;//待排序数组元素的个数，下标从1开始
//1、冒泡排序
void Bubble_sort(int s[],int len){
    bool flag;
    for(int i=1;i<len-1;++i){
        flag=false;
        for(int j=1;j<=len-i;++j)
            if(s[j]>s[j+1]){flag=true;swap(s[j],s[j+1]);}
        if(!flag)break;
    }
}
//2、选择排序
void Select_sort(int s[],int len){
    int k;
    for(int i=1;i<len;++i){
        k=i;
        for(int j=i+1;j<=len;++j)
            if(s[k]>s[j])k=j;
        if(k!=i)swap(s[i],s[k]);
    }
}
//3、插入排序
void Insert_sort(int s[],int len){
    int tmp,j;
    for(int i=2;i<=len;++i){
        tmp=s[i];
        for(j=i-1;j>0&&tmp<s[j];--j);
        for(int k=i;k>j+1;--k)s[k]=s[k-1];
        s[j+1]=tmp;
    }
}
//4、快速排序
int Quick_sort(int s[],int low,int high){
    int tmp=s[low];//首元素是枢轴
    while(low<high){//待排序序列长度大于1
        while(low<high&&tmp<=s[high])--high;//大于枢轴的元素依旧在右边
        s[low]=s[high];//将小于枢轴的元素放左边
        while(low<high&&tmp>=s[low])++low;//小于枢轴的元素依旧在左边
        s[high]=s[low];//将大于枢轴的元素放右边
    }
    s[low]=tmp;//枢轴记录到位
    return low;//返回枢轴的位置
}
void Qsort(int s[],int low,int high){
    if(low<high){
        int key=Quick_sort(s,low,high);
        Qsort(s,low,key-1);
        Qsort(s,key+1,high);
    }
}
//5、希尔排序(采用直接插入)
void Shell_sort(int s[],int len){
    int tmp,j;
    for(int step=len/2;step>0;step/=2){//设置步长
        for(int i=step;i<=len;++i){
            tmp=s[i];
            for(j=i-step;j>0&&tmp<s[j];j-=step);
            for(int k=i;k>j+step;k-=step)s[k]=s[k-step];
            s[j+step]=tmp;
        }
    }
}
//6、归并排序
void Merge(int s[],int t[],int low,int mid,int high){
    int i=low,j=mid+1,k=low;
    while(i<=mid&&j<=high){
        if(s[i]<=s[j])t[k++]=s[i++];
        else t[k++]=s[j++];
    }
    while(i<=mid)t[k++]=s[i++];
    while(j<=high)t[k++]=s[j++];
    for(int i=low;i<=high;++i)s[i]=t[i];//将区间[low,high]拷贝到原来数组s对应的位置，表示该区间元素已排好序
}
void Merge_sort(int s[],int t[],int low,int high){
    if(low<high){
        int mid=(low+high)/2;
        Merge_sort(s,t,low,mid);//递归分成左部分
        Merge_sort(s,t,mid+1,high);//递归分成右部分
        Merge(s,t,low,mid,high);//将两部分归并
    }
}
//7、堆排序(大根堆实现升序排序)
void Heap_Adjust(int s[],int cur,int len){
    int tmp=s[cur];//先取出当前元素cur
    for(int j=2*cur;j<=len;j*=2){//向下筛选
        if(j<len&&s[j]<s[j+1])++j;
        if(tmp>=s[j])break;
        s[cur]=s[j];cur=j;//将子节点j值赋给父节点cur（不用进行交换）
    }
    s[cur]=tmp;
}
void Heap_sort(int s[],int len){
    //1、构建大根堆
    for(int i=len/2;i>0;--i)Heap_Adjust(s,i,len);
    //2.调整堆结构+交换堆顶元素与末尾元素
    for(int i=len;i>1;--i){
        swap(s[i],s[1]);
        Heap_Adjust(s,1,i-1);//将[1,i-1]重新调整为大根堆
    }
}
//8、基数排序
int Max_bit(int s[],int len){//获取数组中最大值的位数
    int dit=1,p=10;
    for(int i=1;i<=len;++i)
        while(s[i]>=p){++dit;p*=10;}
    return dit;
}
void Radix_sort(int s[],int len){
    int exp=1,dit=Max_bit(s,len),*cnt=new int[10],*tmp=new int[len+1];
    for(int j=1;j<=dit;++j){
        for(int i=0;i<10;++i)cnt[i]=0;
        for(int i=1;i<=len;++i)cnt[s[i]/exp%10]++;
        for(int i=1;i<10;++i)cnt[i]+=cnt[i-1];//叠加元素个数
        for(int i=len;i>0;--i)tmp[cnt[s[i]/exp%10]--]=s[i];//将桶中元素倒出来
        for(int i=1;i<=len;++i)s[i]=tmp[i];//将倒出来的元素依次放到原数组中去
        exp*=10;
    }
    delete[]cnt;//释放内存
    delete[]tmp;
}
//打印数组元素值
void print(int s[],int len){
    for(int i=1;i<=len;++i)
        cout<<s[i]<<(i==len?"\n":" ");
}
int main(){
    int *s=new int[len+1];
    int *t=new int[len+1];//t为辅助数组
    srand((unsigned)time(NULL));
    for(int i=1;i<=len;++i)s[i]=rand();
    cout<<"排序前："<<endl;
    print(s,len);//打印原数组
    /*1、冒泡排序
    Bubble_sort(s,len);*/
    /*2、选择排序
    Select_sort(s,len);*/
    /*3、插入排序
    Insert_sort(s,len);*/
    /*4、快速排序
    Qsort(s,1,len);*/
    /*5、希尔排序
    Shell_sort(s,len);*/
    /*6、归并排序
    Merge_sort(s,t,1,len);*/
    /*7、堆排序
    Heap_sort(s,len);*/
    /*8、基数排序
    Radix_sort(s,len);
    cout<<"排序后："<<endl;*/
    print(s,len);//打印排序后的数组元素

    delete[]s;//释放内存
    delete[]t;
    return 0;
}