package Sort;

import java.util.Stack;

public class Sort {
    /** 插入排序
     * 时间复杂度：
     *     最好情况 ： 数据完全有序的时候 1 2 3 4 5 ： O(N)
     *     最坏情况 ： 数据完全逆序的时候 5 4 3 2 1 ： O(N^2)
     *     结论： 当给出的数据 越有序 排列越快
     *
     * 空间复杂度：O(1)
     * 稳定性：稳定的排序
     *        一个本身就稳定的排序 是可以变成不稳定排序的
     *        但是相反 一个本身就不稳定的排序 是不可以变成稳定排序的
     */
    //插入排序 稳定的排序
    public static void inserSort(int[] array){
        for (int i = 1; i < array.length; i++) {
            int tmp = array[i];
            int j = i - 1;
            while(j>=0){
                if(array[j]>tmp){
                    array[j+1] = array[j];
                }else{
                    break;
                }
                array[j] = tmp;
                j--;
            }
        }
    }
    /** 希尔排序
     *     时间复杂度：O(N^1.3)
     *
     */
    //希尔排序
    public static void shellSort(int[] array){
        int gap = array.length;;
        while(gap > 1){
            gap /= 2;
            shell(array,gap);
        }
    }
    public static void shell(int[] array,int gap){
        for (int i = gap; i < array.length; i++) {
            int tmp = array[i];
            int j = i - gap;
            while(j>=0){
                if(array[j]>tmp){
                    array[j+gap] = array[j];
                }else{
                    break;
                }
            }
            array[j+gap] = tmp;
            j-=gap;
        }
    }

    /** 选择排序
     *      时间复杂度：O(N^2)
     *      空间复杂度：O(1)
     *      不稳定排序
     */
    public static void choseSort(int[] array){
        for (int i = 0; i < array.length; i++) {
            int minIndex = i;
            for (int j = i+1; j < array.length; j++) {
                if(array[j]<array[minIndex]){
                    minIndex = j;
                }
            }
            swap(array,i,minIndex);
        }
    }
    public static void swap(int[] array,int i,int j){
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
    public static void choseSort1(int[] array){
        int left = 0;
        int right = array.length-1;
        while(left<right) {
            int minIndex = left;
            int maxIndex = left;
            for (int i = left + 1; i < right; i++) {
                if (array[i] < array[minIndex]) {
                    minIndex = i;
                }
                if (array[i] > array[maxIndex]) {
                    maxIndex = i;
                }
            }
            swap(array,left,minIndex);
            if(maxIndex == left){
                maxIndex = minIndex;
            }
            swap(array,right,maxIndex);
            left++;
            right--;
        }
    }
    /** 堆排序
     *      时间复杂度：O(N*logN)
     *      空间复杂度：O(1)
     *      不稳定排序
     */


    /** 冒泡排序：
     *      时间复杂度：O(N^2) 优化后最好情况：O(N)
     *      空间复杂度：O(1)
     *      稳定性：稳定排序
     */
    public static void bubbleSort(int[] array){
        for (int i = 0; i < array.length-1; i++) {
            boolean flg = false;
            for (int j = 0; j < array.length-1-i; j++) {
                if(array[j]>array[j+1]){
                    swap(array,j,j+1);
                    flg = true;
                }
            }
            if(!flg){
                return;
            }
        }
    }

    /** 快速排序
     *     时间复杂度：
     *          最好的情况：O(N*logN) 满二叉树 或者是 均匀的二叉树
     *          最坏的情况：O(N^2) 单分支的树
     *     空间复杂度：
     *          最好的情况：O(logN)
     *          最坏的情况：O(N)
     *     稳定性：
     *
     *
     *     当数据 太多而且需求量很大的时候 就 容易出现 栈溢出的报错 这里需要优化 如何解决溢出问题？
     */
    public static void quickSort(int[] array){
        quick(array,0,array.length-1);
    }
    public static void quick(int[] array,int start,int end){
        if(start >= end)return;//剩下一个节点或者一个节点都没有了
        //if(end-start+1<=7){inserSortRand(array,start,end);return;}//减少递归次数
        int index = midOfThree(array,start,end);//三数取中
        swap(array,start,index);//保证start 一定是中间大的数字
        int pivot = partition(array,start,end);

        quick(array,start,pivot-1);
        quick(array,pivot+1,end);
    }
    public static int partition(int[] array,int left,int right){
        int key = array[left];
        int i = left;
        //循环让 key的左右 一定 大于或者小于key
         while(left < right){
             //这里就找到了 小于k 的右边的下标
             while(left<right && key <= array[right]){
                  right--;
             }
             //这里就找到了 大于k 的左边边的下标
             while(left<right && key >= array[left]){
                 left++;
             }
             swap(array,left,right);
         }
         //相遇的位置和 i 位置交换
        swap(array,i,left);
        return left;
    }
    //三数取中 (优化快速排序)  避免单分支树的情况 保证 左右两边都有比他大或者比他小的数字
    public static int midOfThree(int[] array,int left,int right){
        int mid = (left+right)/2;
        if(array[left] > array[right]){
            if(array[mid] > array[left]){
                return left;
            }else if(array[mid] < array[right]){
                return right;
            }else{
                return mid;
            }
        }else{
            if(array[mid] < array[left]){
                return left;
            }else if(array[mid] > array[right]){
                return right;
            }else{
                return mid;
            }
        }
    }

    //快速排序优化 挖坑法
    public static int partition2(int[] array,int left,int right){
        int key = array[left];
        //循环让 key的左右 一定 大于或者小于key
        while(left < right){
            //这里就找到了 小于k 的右边的下标
            while(left<right && key <= array[right]){
                right--;
            }
            array[left] = array[right];
            //这里就找到了 大于k 的左边边的下标
            while(left<right && key >= array[left]){
                left++;
            }
            array[right] = array[left];
        }
        //相遇的位置和 i 位置交换
        array[left] = key;
        return left;
    }

    //前后指针法
    public static int partition3(int[] array,int left,int right){
        int prev = left;
        int cur = left+1;
        while(cur <= right){
            if(array[cur]<left && array[++prev]!=array[cur]){
                swap(array,prev,cur);
            }
            cur++;
        }
        swap(array,prev,left);
        return prev;
    }
    //区间内的插排  优化递归次数 但是时间不一定优化
    public static void inserSortRand(int[] array,int begin,int end){
        for (int i = begin+1; i <= end; i++) {
            int tmp = array[i];
            int j = i - 1;
            while(j>=begin){
                if(array[j]>tmp){
                    array[j+1] = array[j];
                }else{
                    break;
                }
            }
            array[j+1] = tmp;
            j--;
        }
    }
    //快速排序的非递归排序
    public static void quickSortNor(int[] array){
        Stack<Integer> stack = new Stack<>();
        int left = 0;
        int right = array.length-1;
        int pivot = partition(array,left,right);
        if(pivot-1>left){
            stack.push(left);
            stack.push(pivot-1);
        }
        if(pivot+1<right){
            stack.push(pivot+1);
            stack.push(right);
        }
        while(!stack.isEmpty()){
            right = stack.pop();
            left = stack.pop();
            pivot = partition(array,left,right);
            if(pivot-1>left){
                stack.push(left);
                stack.push(pivot-1);
            }
            if(pivot+1<right){
                stack.push(pivot+1);
                stack.push(right);
            }
        }
    }

    /**
     * 时间复杂度：O(N*logN)
     * 空间复杂度：O(N)
     * 稳定性：稳定
     * @param array
     */
    public static void mergeSort(int[] array){
        mergeSortFunc(array,0,array.length-1);
    }
    public static void mergeSortFunc(int[] array,int left,int right){
        if(left >= right)return;
        int mid = (left+right)/2;
        mergeSortFunc(array,left,mid);
        mergeSortFunc(array,mid+1,right);
        merge(array,left,right,mid);
    }
    //感觉这里的递归怪怪的
    private static void merge(int[] array, int left, int right, int mid) {
        int s1 = left;
        int s2 = mid+1;
        int[] temArr = new int[right-left+1];
        int k = 0;

        while(s1<=mid && s2 <=right){
            if(array[s1]>=array[s2]){
                temArr[k++] = array[s2++];
            }else{
                temArr[k++] = array[s1++];
            }
        }

        while(s1 <= mid){temArr[k++] = array[s1++];}
        while(s2 <= right){temArr[k++] = array[s2++];}
        //这里的 temArr数组已经是有序数组了

        for (int i = 0; i < temArr.length; i++) {
            array[i+left] = temArr[i];//考虑 右边的排序
        }
    }
    //归并的无递归写法
    public static void mergeSortNor(int[] array){
        int gap = 1;
        while(gap<array.length){
            for (int i = 0; i < array.length; i+=2*gap) {
                int left = i;
                int mid = left+gap-1;
                int right = mid+gap;
                if(mid >= array.length-1){mid = array.length-1;}//如果mid刚刚好是最后一个数 或者比最后一个数大的话
                if(right >= array.length-1){right = array.length-1;}
                merge(array,left,right,mid);
            }
            gap*=2;
        }
    }

    //计数数组 不比较的排序
    public static void countSort(int[] array){
        int minVal = array[0];
        int maxVal = array[0];
        for (int i = 0; i < array.length; i++) {
            if(array[i]<minVal){
                minVal = array[i];
            }
            if(array[i]>maxVal){
                maxVal = array[i];
            }
        }
        int[] count =new int[maxVal-minVal+1];
        for (int i = 0; i < array.length; i++) {
            count[array[i]-minVal]++;
        }
        int index = 0;
        for (int i = 0; i < count.length; i++) {
            while(count[i]>0){
                array[index] = i+minVal;
                index++;
                count[i]--;
            }
        }
    }


    /**
     * 为什么会溢出？
     */

}