package sort_test;

public class test {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] a = {23,54,36,64,7,3,67,85,66,44};
//      int n=a.length;
//      for(int i=n/2-1;i>=0;i--){//i=n/2-1为非叶子结点最后一个父节点
//          build_max_heap(a,i,n);
//      }
        merge_sort(a,0,a.length-1);
        for(int i:a){
            System.out.println(i);
        }
        
//      int nn = binarySearch2(a,36,0,a.length-1);
//      System.out.println(nn);
    }
    
    //is item v less than w?
    private static boolean less(int v,int w){
        return v < w;
    }
    //swap item in array a[] at index i with the one in index j
    private static void exch(int[] a,int i,int j){
        int temp = a[i];
        a[i]=a[j];
        a[j]=temp;
    }
    
    //基本思想：在要排序的一组数中，选出最小的一个数与第一个位置的数交换，然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止
    public static void select_sort(int[] a){
        int n=a.length;
        for(int i=0;i<n;i++){
            int min=i;//先假设最小位置在0
            for(int j=i+1;j<n;j++){//遍历比较位置0和后面任意位置的值，找出最小值的index
                if(less(a[j],a[min])){
                    min=j;
                }
            }
            exch(a,min,i);//把最小值的index和index为i的值对换
        }
    }
    //从第一个数起，比较相邻两数，把较大的放置在后面，一次循环结束，最后一个数最大。除去最后一个数，对前n-1个数重复同样的方法
    public static void bubble_sort(int[] a){
        int n=a.length;
        for(int i=0;i<n-1;i++){
            for(int j=0;j<n-1-i;j++){
                if(less(a[j+1],a[j])){
                    exch(a,j,j+1);
                }
            }
        }
    }
    //前面n-1个数已经是排好的序列，现在要把第n个数查到其中
    public static void insert_sort(int[] a){
        int n=a.length;
        for(int i=0;i<n;i++){
            for(int j=i;j>0;j--){
                if(less(a[j],a[j-1])){
                    exch(a,j-1,j);
                }
            }
        }
    }
    //将未排序部分元素逐个排序插入,但是插入的过程不同,需要每次求一个中间位置,和中间位置元素比较大小,然后根据大小情况,将高位左移或者将低位右移
    public static void binary_insert_sort(int[] a){
        int n=a.length;
        int i,j,temp,low,mid,high;
        for(i=1;i<n;i++){
            low=0;//排序部分的最低位
            temp=a[i];//未排序部分的最低位
            high=i-1;//排序部分的最高位
            while(low<=high){
                mid=(low+high)/2;
                if(a[mid]>temp){
                    high=mid-1;
                }else{
                    low=mid+1;
                }
            }
            for(j=i-1;j>high;j--){//将high+1 ~ i的所有元素后移一位
                a[j+1]=a[j];
            }
            a[high+1]=temp;//插入元素
        }
    }
    //分组的插入排序
    public static void shell_sort(int[] a){
        int n=a.length;
        int h=1;
        while(h<n/3){
            h=3*h+1;//h为步长
        }
        while(h>=1){
            for(int i=h;i<n;i++){
                for(int j=i;j>=h&&less(a[j],a[j-h]);j-=h){
                    exch(a,j,j-h);
                }
            }
            h/=3;
        }
    }
    
    public static void quick_sort(int[] a,int left,int right){
        int ileft=left;
        int iright=right;
        int imiddle=(ileft+iright)/2;
        int temp=a[imiddle];
        
        while(true){
            while(a[iright]>temp) iright--;
            while(a[ileft]<temp) ileft++;
            if(ileft>=iright) break;
            exch(a,ileft,iright);
        }
        if(ileft!=left) quick_sort(a,left,ileft-1);
        if(iright!=right) quick_sort(a,iright+1,right);
    }
    //构建最大堆
    private static void build_max_heap(int[] a,int parent,int length){
        int lchild=2*parent+1;
        int rchild=2*parent+2;
        int largest=parent;
        if(lchild<length&&a[lchild]>a[largest]){
            largest=lchild;
        }
        if(rchild<length&&a[rchild]>a[largest]){
            largest=rchild;
        }
        if(largest!=parent){
            exch(a,largest,parent);
            build_max_heap(a,largest,length);
        }
    }
    public static void heap_sort(int[] a){
        //建堆
        int n=a.length;
        for(int i=n/2-1;i>=0;i--){//i=n/2-1为非叶子结点最后一个父节点
            build_max_heap(a,i,n);
        }
        //已经是最大堆，排序
//      for(int j=n-1;j>0;j--){
//          exch(a,0,j);
//          build_max_heap(a,0,--n);
//      }
        while(n>0){
            exch(a,0,--n);
            build_max_heap(a,0,n);
        }
    }
    
    private static void merge(int[] a,int low,int mid,int high){
        
        int i=low;//左指针
        int j=mid+1;//右指针
        int k=0;
        int[] temp=new int[high-low+1];
        // 把较小的数先移到新数组中 
        while(i<=mid&&j<=high){
            if(a[i]<a[j]){
                temp[k++]=a[i++];
            }else{
                temp[k++]=a[j++];
            }
        }
        // 把左边剩余的数移入数组 
        while(i<=mid){
            temp[k++]=a[i++];
        }
        // 把右边边剩余的数移入数组 
        while(j<=high){
            temp[k++]=a[j++];
        }
        // 把新数组中的数覆盖a数组 
        for(int k2=0;k2<temp.length;k2++){
            a[k2+low]=temp[k2];
        }
    }
    
    public static void merge_sort(int[] a,int low,int high){
        int mid=(low+high)/2;
        if(low<high){
            //左边递归
            merge_sort(a,low,mid);
            //右边递归
            merge_sort(a,mid+1,high);
            merge(a,low,mid,high);
        }
    }
    
    public static int binarySearch(int[] a,int x){
        int low=0;
        int high=a.length-1;
        while(low<=high){
            int middle=(low+high)/2;
            if(x==a[middle]){
                return middle;
            }else if(x<a[middle]){
                high=middle-1;
            }else{
                low=middle+1;
            }
        }
        return -1;
    }
    
    public static int binarySearch2(int[] a,int x,int low,int high){
        if(low<=high){
            int middle=(low+high)/2;
            if(x==a[middle]){
                return middle;
            }else if(x<a[middle]){
                return binarySearch2(a,x,low,middle-1);
            }else{
                return binarySearch2(a,x,middle+1,high);
            }
        }
        return -1;
    }
    

}