public class TestSort {
    //选择排序：它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
    public static void selectSort(int[] a)
    {
        int minIndex=0;
        int temp=0;
        if((a==null)||(a.length==0))
            return;
        for(int i=0;i<a.length-1;i++)
        {
            minIndex=i;//无序区的最小数据数组下标
            for(int j=i+1;j<a.length;j++)
            {
                //在无序区中找到最小数据并保存其数组下标
                if(a[j]<a[minIndex])
                {
                    minIndex=j;
                }
            }
            if(minIndex!=i)
            {
                //如果不是无序区的最小值位置不是默认的第一个数据，则交换之。
                temp=a[i];
                a[i]=a[minIndex];
                a[minIndex]=temp;
            }
        }
    }
    
    //插入排序的基本思想是：每步将一个待排序的纪录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。
    //每次处理就是将无序数列的第一个元素与有序数列的元素从后往前逐个进行比较，找出插入位置，将该元素插入到有序数列的合适位置中。
    public static int[] insertSort(int[] arr){
        if(arr == null || arr.length < 2){
            return arr;//考虑空数组或者不需要排序的情况
        }
        for(int i=1;i<arr.length;i++){
            for(int j=i;j>0;j--){
                if(arr[j]<arr[j-1]){
                    //TODO:
                    int temp=arr[j];
                    arr[j]=arr[j-1];
                    arr[j-1]=temp;
                    }
                else{
                    //接下来是无用功
                    break;
                }
            }
        }
        return arr;
    }
    
    //归并排序:将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间/有序。
    //归并排序的算法我们通常用递归实现，先把待排序区间[s,t]以中点二分，接着把左边子区间排序，再把右边子区间排序，最后把左区间和右区间用一次归并操作合并成有序的区间[s,t]。
    public static void Merge(int array[], int p, int q, int r){
        int i, j, k, n1, n2;
        n1 = q-p+1;
        n2 = r-q;
        int[] L = new int[n1];
        int[] R = new int[n2];
        //左右两部分赋值
        for(i = 0,k=p;i<n1;i++,k++){
            L[i]=array[k];
        }
        for(i=0,k=q+1;i<n2;i++,k++){
            R[i]= array[k];
        }
        //取有序数组L/R中的较大者放入array直至其中一个全部取完
        for(k=p, i=0,j=0;i<n1 && j<n2; k++){
            if(L[i]>R[j]){
                array[k] = L[i];
                i++;
            }
            else{
                array[k] = R[j];
                j++;
            }
        }
        //将L/R剩下的全部复制arrayL中
        if(i<n1){
            for(j=i;j<n1;j++,k++){
                array[k] = L[j];
            }
        }
        if(j<n2){
            for(i=j;i<n2;i++,k++){
                array[k] = R[i];
            }
        }
    }
    
    public static void MergeSort(int array[], int p, int r){
        if(p<r){
            int q = (p+r)/2;
            MergeSort(array, p,q);
            MergeSort(array, q+1,r);
            Merge(array, p, q, r);
        }
    }
    
    //快速排序
    //通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，
    //然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
    
    public static void sort(int array[],int low, int high){
        int i, j;
        int index;
        if(low>=high){
            return;
        }
        i = low;
        j = high;
        index = array[i];                   //第一个元素作为枢轴
        while(i<j){                         //两端向中间扫描
            while(i<j && array[j]>=index){
                j--;
            }
            if(i<j){
                array[i++]=array[j];        //比枢轴小的交换到前段
            }
            while(i<j && array[i] <index){
                i++;
            }
            if(i<j){
                array[j--]=array[i];        //比枢轴大的交换到后端
            }
        }
        array[i]=index;
        sort(array,low,i-1);
        sort(array, i+1,high);
    }
    
    public static void quickSort(int array[]){
        sort(array, 0, array.length-1);
    }
    
    //希尔排序
    //先取一个小于n的整数d1作为第一个增量，把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；
    //然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量   =1，即所有记录放在同一组中进行直接插入排序为止。
    
    public static void shellSort(int array[]){
        int length = array.length;
        int i, j;
        int h;
        int temp;
        for(h = length/2;h>0;h=h/2){            //增量变化
            for(i = h; i<length;i++){           //从i=h开始递增i
                temp = array[i];
                for(j = i-h;j>=0;j-=h){         //从i的位置，往前寻找前面的有序序列中的合适的位置 插入排序
                    if(temp<array[j]){
                        array[j+h]=array[j];                        
                    }
                    else{
                        break;
                    }
                }
                array[j+h]= temp;
            }
        }
    }
    
    /**
     * 希尔排序2
     * @param arrays 需要排序的序列
     */
    public static void sort(int[] arrays){
        if(arrays == null || arrays.length <= 1){
            return;
        }
        //增量
        int incrementNum = arrays.length/2;
        while(incrementNum >=1){
            for(int i=0;i<arrays.length;i++){
                //进行插入排序
                for(int j=i;j<arrays.length-incrementNum;j=j+incrementNum){
                    if(arrays[j]>arrays[j+incrementNum]){
                        int temple = arrays[j];
                        arrays[j] = arrays[j+incrementNum];
                        arrays[j+incrementNum] = temple;
                    }
                }
            }
            //设置新的增量
            incrementNum = incrementNum/2;
        }
    }
    
    
    /**堆排序
     * 堆排序利用了大根堆（或小根堆）堆顶记录的关键字最大（或最小）这一特征，使得在当前无序区中选取最大（或最小）关键字的记录变得简单。
     * 1. 建堆，建堆是不断调整堆的过程，从len/2处开始调整，一直到第一个节点，此处len是堆中元素的个数。
     * 2. 调整堆：调整堆在构建堆的过程中会用到，而且在堆排序过程中也会用到。
     * 3. 堆排序：交换栈顶元素和最后一个元素的位置
     * @param args
     */
    
    // a数组, pos调整起始位置, len调整终止位置
    public static void adjustMinHeap(int[] a, int pos, int len){
        int temp;
        int child;
        for(temp = a[pos]; 2*pos +1<=len; pos=child){
            child = 2 *pos +1;                              //左节点
            if(child <len && a[child]>a[child+1]){          
                child++;                                    //取小的节点
            }
            if(a[child]<temp){                              //顶点放最小的
                a[pos]= a[child];
            }
            else{
                break;                                      //不需要再继续递归
            }
        }
        a[pos] = temp;                                      //放回去
    }
    
    public static void myMinHeapSort(int[] array){
        int i;
        int len = array.length;
        //构建堆
        for(i = len/2-1;i>=0;i--){                  //注意这里要减去1才是正确的
            adjustMinHeap(array, i, len-1);
        }
        for(i=len-1;i>=0;i--){
            //交换
            int tmp = array[0];
            array[0] = array[len-1];
            array[i] = tmp;
            //调整堆
            adjustMinHeap(array, 0, i-1);
        }
        
    }
    
    
    public static void main(String[] args){
        int i = 0;
        int a[] ={5,4,9,8,7,6,0,1,3,2};
//      selectSort(a);
//      insertSort(a);
//      mergeSort(a, 0,1);
//      MergeSort(a, 0, a.length);
//      quickSort(a);
//      shellSort(a);
        sort(a);
        for(i=0;i<a.length;i++){
            System.out.println(a[i]+" ");
        }
        System.out.println("\n");
    }
}