public static void insertSort(int[] arr){
        for(int i=1;i<arr.length;i++){//從第二個(gè)元素開(kāi)始，遍歷整個(gè)數(shù)組
            int j=i-1;//i之前的序列 已經(jīng)有序
            int temp=arr[i];
            for(;j>=0;j--){//此循環(huán)用于尋找插入位置
                if(arr[j]>temp){//此時(shí)逐個(gè)向后移動(dòng)元素
                    arr[j+1]=arr[j];
                }else break;//找到插入位置 直接break
            }
            arr[j+1]=temp;//直接插入
        }
}

public static void hell(int[] arr,int gap){//當(dāng)gap=1時(shí) 其實(shí)就是直接插入排序
        for(int i=gap;i<arr.length;i++){
            int j=i-gap;
            int temp=arr[i];
            for(;j>=0;j-=gap){
                if(arr[j]>temp){
                    arr[j+gap]=arr[j];
                }else break;
            }
            arr[j+gap]=temp;
        }
}
public static void hellSort(int[] arr){
        int gap=arr.length;
        while(gap>1){
            gap=gap/2+1;
            hell(arr,gap);
        }
    }

public static void selectSort(int[] arr){
        for(int i=0;i<arr.length;i++){
            for(int j=i+1;j<arr.length;j++){
                if(arr[j]<arr[i]){
                    int temp=arr[j];
                    arr[j]=arr[i];
                    arr[i]=temp;
                }
            }
      }
}

public static void heapSort(int[] arr){//排序方法
        creatHeap(arr);
        int end=arr.length-1;
    //因?yàn)槭谴蟾?，所以根?jié)點(diǎn)值為最大值，根節(jié)點(diǎn)與最后一個(gè)節(jié)點(diǎn)值交換 輸出并刪除此時(shí)最后一個(gè)節(jié)點(diǎn)，然后向下調(diào)整根節(jié)點(diǎn)
        while(end>0){
            int temp=arr[0];
            arr[0]=arr[end];
            arr[end]=temp;
            shiftDown(arr,0,end);
            end--;
        }

    }
public static void creatHeap(int[] arr){//建堆
        for(int parent=(arr.length-1-1)/2;parent>=0;parent--){
            shiftDown(arr,parent,arr.length);
        }
    }
public static void shiftDown(int[]arr,int root,int len){//向下調(diào)整操作
        int parent=root;
        int child=parent*2+1;
        while(child<len){
            if(child+1<len&&arr[child]<arr[child+1]){//待調(diào)整節(jié)點(diǎn)右子樹(shù)大于左子樹(shù)
                child++;
            }
            if(arr[child]>arr[parent]){//由于是大根堆，如果兒子節(jié)點(diǎn)值大于父親節(jié)點(diǎn)就交換
                int temp=arr[parent];
                arr[parent]=arr[child];
                arr[child]=temp;
                parent=child;//繼續(xù)向下調(diào)整，防止調(diào)整后不滿(mǎn)足大根堆的條件
                child=parent*2+1;
            }else break;
        }
    }

public static void bubbleSort(int[] arr){
        for(int i=0;i<arr.length-1;i++){//外層循環(huán)控制趟數(shù)
            boolean flag=false;//一個(gè)標(biāo)記進(jìn)行優(yōu)化
            for(int j=0;j<arr.length-1-i;j++){//內(nèi)層循環(huán)控制比較次數(shù)
                if(arr[j]>arr[j+1]){
                    int temp=arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=temp;
                    flag=true;
                }
            }
            if(flag==false) break;//如果一趟循環(huán)走完沒(méi)有交換，說(shuō)明已經(jīng)有序，直接break
        }
    }

//該代碼參考acwing創(chuàng)始人yxc的快排模板
public static void quickSort(int[] arr,int l,int r){
        if(l>=r) return;//每次判斷傳進(jìn)來(lái)左右下標(biāo)
        int i=l-1,j=r+1;//因?yàn)樵谘h(huán)中，要先i++，j--所以i，j定義為兩邊界偏移1
        int x=arr[(l+r)/2];//取x為數(shù)組中間位置數(shù)
        while(i<j){
            do i++;while(arr[i]<x);
            do j--;while(arr[j]>x);
            //此時(shí)i指向的數(shù)字大于中軸數(shù)字， j指向數(shù)字小于中軸數(shù)字 交換
            if(i<j){
                int temp=arr[i];
                arr[i]=arr[j];
                arr[j]=temp;
            }
        }
        quickSort(arr,l,j);//退出循環(huán)是i==j 遞歸排序
        quickSort(arr,j+1,r);
    }

public static void mergerSort(int[]arr){
        mergerSortInternal(arr,0,arr.length-1);
    }
public static void mergerSortInternal(int[]arr,int l,int r) {//
        if (l >= r) return;
        int mid = (l + r) / 2;//把數(shù)組分為兩個(gè)
        mergerSortInternal(arr, l, mid);//對(duì)左邊數(shù)組遞歸排序
        mergerSortInternal(arr, mid + 1, r);//對(duì)右邊數(shù)組遞歸排序
        merge(arr,l,mid,r);//排序完成，進(jìn)行合并
    }
 public static void merge(int[]arr,int low,int mid,int high){
        int s1=low;//mid左側(cè)數(shù)組的頭和尾
        int e1=mid;
        int s2=mid+1;//mid右側(cè)數(shù)組的頭和尾
        int e2=high;
        int[]temp=new int[high-low+1];//定義一個(gè)數(shù)字，用來(lái)合并他們
        int k=0;//指示數(shù)組下標(biāo)
        while(s1<=e1&&s2<=e2){//選出兩側(cè)數(shù)組最小元素 插入temp數(shù)組
            if(arr[s1]<=arr[s2]) temp[k++]=arr[s1++];
            else temp[k++]=arr[s2++];
        }
        while(s1<=e1) temp[k++]=arr[s1++];//如果一側(cè)數(shù)組插入完畢，另一側(cè)還有剩余，則全部插入
        while(s2<=e2) temp[k++]=arr[s2++];
        for(int i=0;i<temp.length;i++){//返還到arr數(shù)組
            arr[i+low]=temp[i];
        }
    }
}