public static int [] maopao1(int array[]){
    int t;
    for(int i = 0;i <array.length;i ++){
        for(int j = 0;j < array.length-i-1;j ++){
            if(array[j] < array[j+1]){
                t = array[j+1];
                array[j+1] = array[j];
                array[j] = t;
            }
        }
    }
    return array;
}

//選擇
    public static int [] selectSort(int[] array){
        int t = 0;
        int max = 0;
        for(int i = 0; i < array.length;i ++){
            max = i;
            for(int j = i;j < array.length;j ++){
                if(array[j] > array[max]){
                    max = j;
                }
            }
            //如果i就是max,不用交換位置
            if(i != max){
                t = array[max];
                array[max] = array[i];
                array[i] = t;
            }
        }
        return array;
    }

//快速排序:分而治之的思想,一左一右兩個指針,以left為基準
    public static void quickSort(int left,int right,int [] arr){
        //從小到大排序
        int i = left;
        int j = right;
        //注意:i也不能等于j,當(dāng)i==j說明排序完成,最后一次的左/右部分只有一個數(shù)字
        if(i >= j)
            return ;
        //定義一個基準值
        int k = arr[left];
        while(i != j){
            //i不能大于j
            if(arr[i] <= k && i < j){
                i++;
            }
            if(arr[j] > k && i < j){
                j --;
            }
            if(i < j){
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        //i == j
        if(k > arr[i]){
            int temp = arr[left];
            arr[left] = arr[i];
            arr[i] = temp;
        }
        //遞歸
        quickSort(left,i-1,arr);
        quickSort(i,right,arr);
    }

//歸并排序:先分割,再合并
    //分割
    public static int [] separate(int [] arr){
        if(arr.length < 2){
            return arr;
        }
        //找中位數(shù),Math.floor(a)得到小于a的最大整數(shù)
        //可能數(shù)組數(shù)量為奇數(shù)的情況下
        int mid = (int)Math.floor(arr.length/2);
        //分成兩個
        int [] left = Arrays.copyOfRange(arr,0,mid);//(左閉右開]
        int [] right = Arrays.copyOfRange(arr,mid,arr.length);//因為下標從0開始,所以本來就取不到arr.length,不用減一
        //遞歸
        return merge(separate(left),separate(right));
    }
    //合并
    public static int [] merge(int [] left,int [] right){
        int [] arr = new int[left.length+right.length];
        if(arr.length < 2){
            //判斷如果數(shù)組長度小于2,那么必定其中一個數(shù)組有值,一個無值,返回有值的即可
            return left.length == 0?right:left;
        }
        int i=0,j=0,k=0;
        while(i<left.length && j<right.length){
            //把小的那個數(shù)組添加到新數(shù)組中
            if(left[i] < right[j]){
                arr[k++] = left[i++];
            }else{
                arr[k++] = right[j++];
            }
        }
        //最后還有一個沒有添加到arr新數(shù)組中,這時加上去
        while(i < left.length){
            arr[k++] = left[i++];
        }while(j < left.length){
            arr[k++] = right[j++];
        }
        return arr;
    }

public static void insertSortAsc(int [] arr){
        for(int i=1;i<arr.length;i++){
            int temp=arr[i];//temp哨兵位置
            int index=i-1;//index代表與哨兵比較的值的下標
            //index不能小于0&&升序,把index指向的數(shù)值與哨兵作比較,如果哨兵小于index指向的元素
            while(index >=0 && arr[index] > temp){
                //把index指向的元素后移一位
                arr[index+1] = arr[index];
                index --;//index--確保從已經(jīng)排好的元素中選擇,從后往前掃描
            }
            //這時,在拍排的序列中,比哨兵大的元素都已在哨兵右邊,此時把哨兵放到index+1位置上即可
            arr[index+1] = temp;
        }
    }

public static void shellSortAsc(int[] arr){
        int gap=arr.length/2;//增量,初始為數(shù)組長度一半
        while(gap>=1){
            for(int i=gap;i<arr.length;i++){//這里其實就是插入排序,不過把原來的i=1變成i=gap
                int temp=arr[i];
                int index=i-gap;
                while(index>=0&&arr[index]>temp){
                    arr[index+gap]=arr[index];
                    index=index-gap;
                }
                arr[index+gap]=temp;
            }
            gap=gap/2;//增量遞減
        }
    }