//冒泡排序：

public static void maopao(){
    int[]a={1,3,2,5,9,8,7};
    for (int i=0;i<a.length-1;i++){
        for (int j=0;j< a.length-i-1;j++){
            if (a[j]>a[j+1]){
                a[j]=a[j]^a[j+1];
                a[j+1]=a[j+1]^a[j];
                a[j]=a[j]^a[j+1];
            }
        }
    }
}

//基数排序：

public static void jishu(int[]arr){
        if(arr.length<=1)
            return;
        int max=0;
        for (int i=0;i<arr.length;i++){
            if(max<arr[i]){
                max=arr[i];
            }
        }
        int maxDight=1;
        while (max/10>0){
            maxDight++;
            max=max/10;
        }
        int[][]tong=new int[10][arr.length];
        int base=10;
        for (int i=0;i<maxDight;i++){
            int[]tonglength=new int[10];
            for (int j=0;j<arr.length;j++){
                int whichtong=(arr[j]%base)/(base/10);
                tong[whichtong][tonglength[whichtong]]=arr[j];
                tonglength[whichtong]++;
            }
            int k=0;
            for (int b=0;b< tong.length;b++){
                for (int p=0;p<tonglength[b];p++){
                    arr[k++]=tong[b][p];
                }
            }
        }
    }

//堆排序：

public static void max_heapify(int[]a,int n){
    int child;
    for (int i=(n-1)/2;i>=0;i--){
        child=2*i+1;
        if(child!=n&&a[child]<a[child+1]){
            child++;
        }
        if(a[i]<a[child]){
            int temp=a[i];
            a[i]=a[child];
            a[child]=temp;
        }
    }
}
public static void dui(int[]a){
    for (int i=a.length-1;i>0;i--){
        max_heapify(a,i);
        int temp=a[0];
        a[0]=a[i];
        a[i]=temp;
    }
}

//希尔排序：

public static void xier(int[]a){
    int length=a.length;
    int h=1;
    while (h<a.length/3) h=3*h+1;
    for (;h>=1;h/=3){
        for (int i=0;i<a.length-h;i+=h){
            for (int j=i+h;j>0;j-=h){
                if (a[j] < a[j - h]) {
                int temp = a[j];
                a[j] = a[j - h];
                a[j - h] = temp;
            }
            }
        }
    }
}

//归并排序：

private static int[] aux;
public static void sort(int[]a){
    aux=new int[a.length];
    sort(a,0,a.length-1);
    System.out.println(Arrays.toString(a));
}
public static void sort(int[]a,int low,int high){
    if(low>=high){
        return;
    }
    int mid=(low+high)/2;
    sort(a,low,mid);//
    sort(a,mid+1,high);//
    guibing(a,low,mid,high);
}

public static void guibing(int[]a,int low,int mid,int high){
    int i=low,j=mid+1;
    for (int k=low;k<=high;k++){
        aux[k]=a[k];
    }
    for (int k=low;k<=high;k++){
        if(i>mid){
            a[k]=aux[j++];
        }else if(j>high){
            a[k]=aux[i++];
        }else if(aux[j]<aux[i]){
            a[k]=aux[j++];
        }else {
            a[k]=aux[i++];
        }
    }
}

//快速排序：

public static void main(String[] args) {
    int[] arr = { 49, 38, 65, 97, 23, 22, 76, 1, 5, 8, 2, 0, -1, 22 };
    quickSort(arr, 0, arr.length - 1);
    System.out.println("排序后:");
    for (int i : arr) {
        System.out.print(i+" ");
    }
}

private static void quickSort(int[] arr, int low, int high) {
    if (low < high) {
        int index = getIndex(arr, low, high);
        quickSort(arr, low, index - 1);
        quickSort(arr, index + 1, high);
    }

}
private static int getIndex(int[] arr, int low, int high) {
    int tmp = arr[low];
    while (low < high) {
        while (low < high && arr[high] >= tmp) {
            high--;
        }
        arr[low] = arr[high];
        while (low < high && arr[low] <= tmp) {
            low++;
        }
        arr[high] = arr[low];

    }
    arr[low] = tmp;
    return low;
}

//插入排序：

public static void charu(int[]nums){
    for (int i=1;i<nums.length;i++){
        int temp=nums[i];
        int insertPost=-1;
        for (int j=i-1;j>=0;j--){
            if(temp<nums[j]){
                nums[j+1]=nums[j];
                insertPost=j;
            }else {
                break;
            }
        }
        if(insertPost!=-1){
            nums[insertPost]=temp;
        }
    }
}

//选择排序：

public static void xuanze(){
    int[] arr = {5, 4, 7, 1, 8, 2, 3, 6, 9};
    for (int i = 0; i < arr.length ; i++) {
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[i] >arr[j]) {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
    }
}