package sort;

public class Sort {
    public static void BubbleSort(int[] arr) {
        //TODO 冒泡排序
        for(int i=arr.length-1;i>0;i--) {
            for(int j=0;j<i;j++) {
                if(arr[j]<arr[j+1]) {
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
    }
    public static void InsertSort(int[] arr) {
        //TODO 插入排序
        for(int i=1;i<arr.length;i++) {
            int temp = arr[i];
            int index = i-1;
            while(index>=0 && arr[index]>temp) {
                arr[index+1] = arr[index];
                index--;
            }
            arr[index+1] = temp;
        }
    }
    public static void ShellSort(int[] arr) {
        //TODO 希尔排序
        for(int r = arr.length/2;r>=1;r=r/2) {
            for(int i=r;i<arr.length;i++) {
                int j=i-r;
                int temp = arr[i];
                while(j>=0 && arr[j]>temp) {
                    arr[j+r] = arr[j];
                    j-=r;
                }
                arr[j+r] = temp;
            }
        }
    }
    public static void Heapsort(int[] arr) {
        //TODO 堆排序
        for(int i=arr.length/2-1;i>=0;i--) {
            Perdown(arr,i,arr.length);
        }
        for(int j=arr.length-1;j>=0;j--) {
            int temp = arr[j];
            arr[j] = arr[0];
            arr[0] = temp;
            Perdown(arr,0,j);
        }
    }
    public static void Perdown(int[] arr,int i,int length) {
        int child = 0;
        int j;
        int temp = arr[i];
        for(j=i;j*2+2<=length-1;j=child) {
            child = j*2+1;
            if(child!=length-1 && arr[child]<arr[child+1]) {
                child++;
            }
            if(arr[child]>temp) {
                arr[j] = arr[child];
            }else {
                break;
            }
        }
        arr[j] = temp;
    }
    public static void MergeSort(int[] arr){
        //TODO 归并排序
        int[]tmp = new int[arr.length];
        MSort(arr,tmp,0,arr.length-1);
    }
    public static void MSort(int[]arr,int[]tmp,int left,int right){
        int center;
        if (left<right){
            center = (right+left)/2;
            MSort(arr,tmp,left,center);
            MSort(arr,tmp,center+1,right);
            merge(arr,tmp,left,center+1,right);
        }
    }
    public static void merge(int[]arr,int[]tmp,int left,int center,int right){
        int start = left;
        int leftEnd = center-1;
        int length = right-left+1;
        while (left<=leftEnd && center<=right){
            if (arr[left]<arr[center]){
                tmp[start++] = arr[left++];
            }else {
                tmp[start++] = arr[center++];
            }
        }
        while (left<=leftEnd){
            tmp[start++] = arr[left++];
        }
        while (center<=right){
            tmp[start++] = arr[center++];
        }
        for (int i=0;i<length;i++,right--){
            arr[right] = tmp[right];
        }
    }
    public static void QuickSort(int[] arr){
        //TODO 快速排序
        QSort(arr,0,arr.length-1);
    }
    public static void QSort(int[] arr,int low,int high){
        if (low>high){
            return;
        }
        int i =low;
        int j = high;
        int tmp = arr[low];
        while (i<j){
            //先看右面
            while (arr[j]>=tmp && i<j){
                j--;
            }
            //再看左面
            while (arr[i]<=tmp && i<j){
                i++;
            }
            //交换
            if (i<j){
                int a = arr[i];
                arr[i] = arr[j];
                arr[j] = a;
            }
        }
        arr[low] = arr[i];
        arr[i] = tmp;
        QSort(arr,low,i-1);
        QSort(arr,i+1,high);
    }
    public static void main(String[] args) {
        int[] test = {2,5,1,0,6,7,3};
        QuickSort(test);
        for(int i=0;i<test.length;i++) {
            System.out.print(test[i]);
        }
    }
}