//C++
typedef int ElemType;
class SortType{
    public:
        ll cnt;
        SortType():cnt(0){}
    public:
        void print(ElemType a[],int n){
            for(int i=0;i<n;i++){
                if(i==0)    cout<<a[i];
                else    cout<<","<<a[i];
            }
            puts("");
        }
        /*
        *   直接插入排序,时间复杂度O(n^2)
        *   每次将一个数字插入到已经有序的数组中去,插入的过程是现有的数字向后移动
        *   稳定排序
        */
    public:
        void InsertSort(ElemType a[],int n,int ti=1){
            for(int i = ti ; i<n ; i++){
                if(a[i]<a[i-ti]){
                    ElemType x = a[i] ;
                    int j;
                    for(j = i;j>=ti && x<a[j-ti];j-=ti)
                        a[j] = a[j-ti];
                    a[j]=x;
                }
            }
            return ;
        }
        /*
        *   希尔排序,先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序
        *   选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
        *   按增量序列个数k，对序列进行k 趟排序;
        *   由原先的直接插入排序每次间隔1,变成了每次间隔为ti
        *   希尔排序的时间复杂度与增量序列的选取有关 最好情况O(nlog2n)
        *   非稳定排序
        */
    public:
        void ShellSort(ElemType a[],int n){
            int ti = n>>1;
            while(ti>=1){
                this->InsertSort(a,n,ti);
                ti>>=1;
            }
            return ;
        }
        /*
        *   选择法排序
        *   每次选取该数字之后最小的数与之交换
        *   时间复杂度O(n^2) 不稳定排序
        */
    public:
        void SelectSort(ElemType a[],int n){
            for(int i = 0;i<n;i++){
                int k = i;
                for(int j = i+1;j<n;j++)
                    if(a[j]<a[k])
                        k = j;
                if(k!=i)
                    swap(a[i],a[k]);
            }
            return ;
        }
        /*
        *   冒泡排序,时间复杂度O(n^2)
        *   稳定排序
        */
    public:
        void BubbleSort(ElemType a[],int n){
            int flag=1;
            for(int i = 1;i<n&&flag;i++){
                flag = 0;
                for(int j=0;j<n-i;j++)
                    if(a[j]>a[j+1]){
                        swap(a[j],a[j+1]);
                        flag = 1;
                    }
            }
            return;
        }
        /*
        *   快速排序时间复杂度：O（n*logn）最坏：O（n^2）
        *   不稳定排序
        */
    public:
        void QuickSort(ElemType a[],int l,int r){
            if(l>=r)    return;
            int mid = Partition(a,l,r);
            QuickSort(a,l,mid-1);
            QuickSort(a,mid+1,r);
            return;
        }
    private:
        int Partition(ElemType a[],int l,int r){
            int mid = l;
            for(int i = l+1;i<=r;i++)
                if(a[i]<a[l])
                    swap(a[++mid],a[i]);
            swap(a[l],a[mid]);
            return mid;
        }
        /*
        *   归并排序,时间复杂度O(nlogn)
        *   分治的思想,先都划分成小的集合,两两合并。
        *   49 38 65 97 76 13 27
        *   [39 49] [65 97] [13 76] [27]   -- 第一趟
        *   [39 49 65 97] [13 27 76]       -- 第二趟
        *   [13 27 39 49 65 76 97]         -- 第三趟
        *   稳定排序
        */
    public:
        void MergeSort(ElemType a[],ElemType b[],int l,int r){
            if(l>=r)    return;
            int mid = l+((r-l)>>1);
            MergeSort(a,b,l,mid);
            MergeSort(a,b,mid+1,r);
            this->Merge(a,b,l,mid,r);
        }
    private:
        void Merge(ElemType a[],ElemType b[],int l,int mid,int r){
            int i = l, j = mid+1 , k = l;
            while(i<=mid&&j<=r){
                if(a[i]<=a[j])
                    b[k++]=a[i++];
                else{
                    b[k++]=a[j++];
                    //  cnt += mid - i + 1;
                }
            }
            while(i<=mid)   b[k++] = a[i++];
            while(j<=r)     b[k++] = a[j++];
            for(i = l;i<=r;i++)
                a[i] = b[i];
        }
        /*
        *   堆排序,时间复杂度O(nlogn)
        *   不稳定排序
        */
    public:
        void HeapSort(ElemType a[],int n){
            BuildMaxHeap(a,n);
            for(int i = n-1;i>=1;i--){
                swap(a[i],a[0]);
                MaxHeapify(a,0,i);
            }
            return;
        }
        /**
         *  从每个非叶子节点开始,然后向其左右孩子推进,
         *  如果发现一方大于自己,则进行交换 
         */
    private:
        void BuildMaxHeap(ElemType a[],int n){
            for(int i = (n-1)/2;i>=0;i--){
                MaxHeapify(a,i,n);
                //MaxHeapify2(a,i,n);
            }
        }
    private:
        void MaxHeapify(ElemType a[],int i,int n){
            int l = 2*i+1 , r = 2*i+2;
            int maxx = i;
            if(l<n && a[l]>a[maxx])    maxx = l;
            if(r<n && a[r]>a[maxx])    maxx = r;
            if(i!=maxx){
                swap(a[i],a[maxx]);
                MaxHeapify(a,maxx,n);
            }
        }
        void MaxHeapify2(ElemType a[],int s,int n){
            int mid = a[s];
            for(int i = 2*s+1;i<n;i=2*i+1){
                if(i+1<n&&a[i]<a[i+1])
                    i++;
                if(mid>a[i])    break;
                a[s] = a[i];
                s = i;
            }
            a[s] = mid;
            return;
        }
        /**
        *   基数排序,时间复杂度O(logB(N)·n) 整数排序算法
        *   基数排序的方式可以采用LSD（Least significant digital）
        *   或MSD（Most significant digital），
        *   LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。
        *   稳定排序
        */
    public:
        void RadixSort(ElemType a[],int n){
            //base on LSD.
            int maxbit = getmaxbit(a,n);
            int *num = new int[10];
            int *tmp = new int[n];
            int radix = 1;
            for(int i = 1; i<=maxbit; i++){
                for(int j = 0; j<10 ;j++)
                    num[j] = 0;
                for(int j = 0;j<n;j++){
                    int b = (a[j]/radix)%10;
                    num[b]++;
                }
                for(int j=1 ;j<10;j++)
                    num[j] += num[j-1];
                for(int j=n-1;j>=0;j--){
                    int b = (a[j]/radix)%10;
                    tmp[num[b]-1] = a[j];
                    num[b]--;
                }
                for(int j = 0;j<n;j++)
                    a[j] = tmp[j];
                radix*=10;
            }
            delete []tmp;
            delete []num;
        }
    private:
        int getmaxbit(ElemType a[],int n){
            int maxbit = 1, temp = 10;
            for(int i = 0; i<n; i++){
                while(a[i]>=temp){
                    temp*=10;
                    maxbit++;
                }
            }
            return maxbit;
        }
 };

int main()
{
    SortType *s = new SortType();
    ElemType a[110];
    srand(time(NULL));
    int n;
    n = rand()%100 + 1;
    for(int i = 0;i<n;i++)
        a[i] = rand()%99999+1;
    s->InsertSort(a,n);
    s->print(a,n);
    s->HeapSort(a,n);
    s->print(a,n);
}