#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
//1插入排序
//1.1直接插入排序
void insertSort(int a[],int n){
    int i,j,temp;
    for(int i=1;i<n;i++){
        if(a[i]<a[i-1]){
            temp=a[i];
            for(j=i-1; j>=0&&temp<a[j];j--)
                a[j+1]=a[j];

            a[j+1]=a[j];
        }
    }
} 
//1.2折半插入
void half_insertSort(int a[],int n){
    int i,j,low,high,mid,temp;
    for(i=1;i<n;i++){//从前往后依次选数插入 
        temp=a[i];

        low=0;high=i-1;//每次都是搜索所有a[i]前面的数 
        while(low<=high){//从a[i]前面的数组中，把a[i]锁定在low~high之间，high右边的都比他大，low左边的都比他小 
            mid=(low+high)/2;
            if(temp>a[mid])low=mid+1;
            else high=mid-1;    
        }

        for(j=i-1;j>high;j--)
            a[j+1]=a[j];

        a[high+1]=temp;
    }
} 
//1.3希尔排序 
void shellSort(int a[],int n){
    int temp,i,j,d;
    for(d=n/2;d>=1;d/=2){//步长 
        //接下来在每组内部进行插入排序 
        for(i=d;i<n;i+=d){//
            if(a[i]<a[i-d]){
                temp=a[i];
                for(j=i-d ; temp<a[j]&&j>=0 ; j-=d)//往前找比他小的，放在其后面 
                    a[j+d]=a[j];//后移，让位 

                a[j+d]=temp;//找到了位置，放入 
            }
        }
    }
}

//2交换排序
//2.1冒泡排序
void bubbleSort(int a[],int n){
    int i,j,temp;
    for(int i=0;i<n;i++){
        for(j=i+1;j<n;j++){
            if(a[j]<a[i]){
                temp=a[i];
                a[i]=a[j];
                a[j]=temp;
            }
        }
    }
} 
//2.2快速排序1
int Partition(int a[],int left,int right){
    int temp=a[left];
    while(left<right){
        while(left<right && a[right]>temp)right--;
        a[left]=a[right];
        while(left<right && a[left]<temp)left++;
        a[right]=a[left];
    }
    a[left]=temp;//把temp放到两指针相遇的地方 
    return left;//返回左右指针相遇的地方 
}
void quickSort1(int a[],int left,int right){
    if(left<right){
        int pos=Partition(a,left,right);
        quickSort1(a,left,pos-1);
        quickSort1(a,pos+1,right);
    }
} 
//2.2快速排序2
void quickSort2(int a[],int left,int right){
    if(left>=right)return;

    int i=left-1,j=right+1;
    int temp=a[left];//或者left+right>>1 
    while(i<j){
        do i++;while(a[i]<temp);
        do j--;while(a[j]>temp);

        if(i<j)swap(a[i],a[j]);     
    }
    quickSort2(a,left,j);
    quickSort2(a,j+1,right);
} 

//3选择排序
//3.1简单选择排序
void selectSort(int a[],int n){
    int i,j,min;
    for(i=0;i<n-1;i++){
        min=i;
        for(j=i+1;j<n;j++)
            if(a[j]<a[min])min=j;

        if(min!=i)swap(a[i],a[min]);
    }
} 
//3.2堆排序
void HeadAdjust(int a[],int k,int n){//对以k为根的子树进行调整  ！其实是up的过程 
    int temp=a[k];//temp暂存子树的根节点

    for(int i=2*k;i<n;i*=2){//有点深度优先遍历的赶脚 !k是父亲，i是儿子 
        if(i<n && a[i]<a[i+1])i++;//取值较大的子节点的下标 
        if(temp>=a[i])break;
        else{//没找到比根大的 
            a[k]=a[i];//将a[i]调整到双亲节点上  ！k是根节点的下标 
            k=i;//接下来以i的位置为根的子树继续找 
        }
    } 

    a[k]=temp;

}
void BuildMaxHeap(int a[],int n){
    for(int i=n/2;i>=0;i--){//i从n/2到0，反复调整堆  !最后一个结点是 n/2结点 的孩子 
                            //从小子树到大子树，依次调整！建堆肯定从小到大建哇 
        HeadAdjust(a,i,n);
    }
}
void heapSort(int a[],int n){
    BuildMaxHeap(a,n);
    for(int i=n-1;i>0;i--){//n-1趟交换和建堆过程  ！从最后一个结点到根节点的下一个位置 
        swap(a[i],a[0]);//每次堆顶元素都和最后一个元素交换，然后向上调整 
                        //把最小值放到前面！类比简单选择排序  
        HeadAdjust(a,0,i-1);//把剩余i-1个元素整理成堆  !大三角到小三角 
                            //关于i-1:i号此时存的是最大的，已经排好序了，不必参与堆排序的调整 
    }
} 

//4归并排序
void Merge(int a[],int low,int mid,int high){
    int b[100];
    int i,j,k;
    for(i=low;i<=high;i++)b[i]=a[i];
    for(i=low,j=mid+1,k=i;i<=mid && j<=high;k++){
        b[i]<=b[j] ? a[k]=b[i++]:a[k]=b[j++];
    }

    while(i<=mid)a[k++]=b[i++];
    while(j<=high)a[k++]=b[j++];
}
void mergeSort(int a[],int low,int high){
    if(low<high){
        int mid=(low+high)/2;
        mergeSort(a,low,mid);
        mergeSort(a,mid+1,high);
        Merge(a,low,mid,high);
    }
} 

//5基数排序
//通常是链式基数排序 

int main(){
    int a[8]={8,37,56,5,4,35,2,41};
    int n=sizeof(a)/sizeof(a[0]);

    //insertSort(a,n);cout<<"直接插入排序:"<<endl;
    //half_insertSort(a,n);cout<<"折半插入排序:"<<endl;
    //shellSort(a,n);cout<<"希尔排序:"<<endl;

    //bubbleSort(a,n);cout<<"冒泡排序:"<<endl;
    //quickSort1(a,0,n-1);cout<<"快速排序1:"<<endl;
    //quickSort2(a,0,n-1);cout<<"快速排序2:"<<endl;

    //selectSort(a,n);cout<<"简单选择排序:"<<endl;
    //heapSort(a,n);cout<<"堆排序:"<<endl;

    mergeSort(a,0,n-1);cout<<"归并排序:"<<endl;

    for(int i=0;i<n;i++){
        cout<<a[i]<<" ";
    }cout<<endl;

    return 0;
}