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

public static void hell(int[] arr,int gap){//當gap=1時 其實就是直接插入排序
        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;
    //因為是大根堆，所以根節(jié)點值為最大值，根節(jié)點與最后一個節(jié)點值交換 輸出并刪除此時最后一個節(jié)點，然后向下調整根節(jié)點
        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){//向下調整操作
        int parent=root;
        int child=parent*2+1;
        while(child<len){
            if(child+1<len&&arr[child]<arr[child+1]){//待調整節(jié)點右子樹大于左子樹
                child++;
            }
            if(arr[child]>arr[parent]){//由于是大根堆，如果兒子節(jié)點值大于父親節(jié)點就交換
                int temp=arr[parent];
                arr[parent]=arr[child];
                arr[child]=temp;
                parent=child;//繼續(xù)向下調整，防止調整后不滿足大根堆的條件
                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;//一個標記進行優(yōu)化
            for(int j=0;j<arr.length-1-i;j++){//內層循環(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)走完沒有交換，說明已經有序，直接break
        }
    }

//該代碼參考acwing創(chuàng)始人yxc的快排模板
public static void quickSort(int[] arr,int l,int r){
        if(l>=r) return;//每次判斷傳進來左右下標
        int i=l-1,j=r+1;//因為在循環(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);
            //此時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ù)組分為兩個
        mergerSortInternal(arr, l, mid);//對左邊數(shù)組遞歸排序
        mergerSortInternal(arr, mid + 1, r);//對右邊數(shù)組遞歸排序
        merge(arr,l,mid,r);//排序完成，進行合并
    }
 public static void merge(int[]arr,int low,int mid,int high){
        int s1=low;//mid左側數(shù)組的頭和尾
        int e1=mid;
        int s2=mid+1;//mid右側數(shù)組的頭和尾
        int e2=high;
        int[]temp=new int[high-low+1];//定義一個數(shù)字，用來合并他們
        int k=0;//指示數(shù)組下標
        while(s1<=e1&&s2<=e2){//選出兩側數(shù)組最小元素 插入temp數(shù)組
            if(arr[s1]<=arr[s2]) temp[k++]=arr[s1++];
            else temp[k++]=arr[s2++];
        }
        while(s1<=e1) temp[k++]=arr[s1++];//如果一側數(shù)組插入完畢，另一側還有剩余，則全部插入
        while(s2<=e2) temp[k++]=arr[s2++];
        for(int i=0;i<temp.length;i++){//返還到arr數(shù)組
            arr[i+low]=temp[i];
        }
    }
}