public class BubblingSort {
    public static void sort(int[] arr){
        int length = arr.length;
        while (length>0){
            for(int i=1;i<length;i++){
                if(arr[i-1]>arr[i]){
                    //如果左边的比右边的大，则交换左右的位置，即将大的向上冒
                    U.swap(arr,i-1,i);
                }
            }
            length--;
        }
    }
}

public class SelectorSort {

    public static void sort(int[] arr){
        if(null==arr)
            throw new IllegalArgumentException("参数错误");
        for(int i=0; i<arr.length; i++){
            //找到i至最后一个元素中最小的元素的所在索引
            int min = i;
            for(int j=i+1;j<arr.length-1;j++){
                if(arr[j] < arr[min]){
                    min = j;
                }
            }
            //将最小的元素交换值i的位置
            U.swap(arr,i,min);
        }
    }
}

public class InsertSort{

    /**
     * 思路：从第二个开始逐步向后遍历，并且插入到前面的指定位置，将该位置的元素向后移动，
     * @param arr
     */
    public static void sort(int[] arr){
        for(int i=1;i<arr.length;i++){
            //将当前元素插入到前面的有序集合中
            //1.定位到位置
            int index = find(arr,0,i-1,arr[i]);
            //2.将该位置的元素后移一位，且将该元素插入到该位置
            insertIndex(arr,index,i-1,arr[i]);
        }
    }

    private static int find(int[] arr,int left,int right,int value){
        //如果比最右边的还大，则位置不变
        if(value >= arr[right]){
            return right+1;
        }
        //如果比最左边的还小，则为最左边位置
        if(value <= arr[left]){
            return left;
        }
        //在中间的情况
        while (right > left){
            if(arr[right]==value || arr[right-1]==value){
                return right;
            }else if(arr[right] > value && arr[right-1] < value){
                return right;
            }
            right--;
        }
        throw new IllegalArgumentException("未找到元素位置");
    }

    private static void insertIndex(int[] arr,int index,int right,int value){
        //从后向前移动
        while (right >= index){
            U.swap(arr,right,right+1);
            right--;
        }
        arr[index] = value;
    }

    public static void sort_simulate(int[] arr){
        for(int i=1;i<arr.length;i++){
            int j = i;
            while (j>0 && arr[j] < arr[j-1]){
                U.swap(arr,j,j-1);
                j--;
            }
        }
    }

    /**
     * 相对于我自己的思路，书上的思路更加优雅，代码量也比较少，
     * 思路：对于 1 到 N-1 之间的每一个 i，将 a[i] 与 a[0] 到 a[i-1] 中比它小的所有元素依次有序地交换。
     * 在索引 i 由左向右变化的过程中，它左侧的元素总是有序的，所以当 i 到达数组的右端时排序就完成了。
     * @param arr
     */
    public static void sort_book(int[] arr){
        for(int i=1;i<arr.length;i++){
            for(int j=i;j>0 && arr[j]<arr[j-1];j--){
                U.swap(arr,j,j-1);
            }
        }
    }

}

public class ShellSort {
    /**
     * 本人思路：首先设计间隔为h，例如h=3，那么以3为间隔将arr分成多个数组，如索引号分别是[0,3,6,9][1,4,7,10][2,5,8]
     * 将这三个索引的数组排序完成后，逐步减少h的值，此时是2，则需要使用插入排序的数组索引号是[0,2,4,6,8,10][1,3,5,7,9]
     * 然后将间隔为2的数组拍完序后，将h缩减为1，再使用插入排序的数组索引号是[0,1,2,3,4,5,6,7,8,9,10]，
     * 主要**是插入排序逐步的移动元素效率太低，通过间隔的方式，扩大元素移动的范围，逐步的将无序数组转变成大致有序最终由于，
     * 主要是利用插入排序的特点，插入排序的特点是数组如果有序，则插入排序的元素交换次数就会比较少，效率就会很高
     * @param arr
     */
    public static void sort(int[] arr){
        int h = arr.length/3;
        while (h>0){
            for(int i=0;i<arr.length;i++){
                int j = i;
                while (j>=0 && (j+h)<arr.length && arr[j+h]<arr[j]){
                    U.swap(arr,j,j+h);
                    j-=h;
                }
            }
            h--;
        }
    }
}

public class Merge {

    /**
     * 实现归并的一种直截了当的办法是将两个不同的有序数组归并到第三个数组中，
     * 但是，当用归并将一个大数组排序时，我们需要进行很多次归并，因此在每次归并时都创建一
     * 个新数组来存储排序结果会带来问题。我们更希望有一种能够在原地归并的方法，这样就可以先将
     * 前半部分排序，再将后半部分排序，然后在数组中移动元素而不需要使用额外的空间。
     * merge(a, lo,mid, hi)，它会将子数组 a[lo..mid] 和 a[mid+1..hi] 归并成一个有序的数组并将结果存放在 a[lo..hi] 中。
     *
     */
    private static void merge(int[] a,int lo,int mid,int hi){
        int i = lo, j = mid+1;
        for (int k = lo; k <= hi; k++) // 将a[lo..hi]复制到aux[lo..hi]
            aux[k] = a[k];
        for (int k = lo; k <= hi; k++) // 归并回到a[lo..hi]
            if (i > mid) {
                a[k] = aux[j++];
            } else if (j > hi ) {
                a[k] = aux[i++];
            } else if (aux[j] < aux[i]) {
                a[k] = aux[j++];
            } else {
                a[k] = aux[i++];
            }
    }


    private static int[] aux; // 归并所需的辅助数组

    public static void sort(int[] a)
    {
        aux = new int[a.length]; // 一次性分配空间
        sort(a, 0, a.length - 1);
    }
    private static void sort(int[] a, int lo, int hi)
    { // 将数组a[lo..hi]排序
        if (hi <= lo) return;
        int mid = lo + (hi - lo)/2;
        sort(a, lo, mid); // 将左半边排序
        sort(a, mid+1, hi); // 将右半边排序
        merge(a, lo, mid, hi); // 归并结果（代码见“原地归并的抽象方法”）
    }
}

public class MyMerge {

    /**
     * 思路：采用分治递归的**，将数组递归拆分两半，然后将左右两边的数组排完序后，再将两边数组合并成为一个新的有序数组
     * 1.主函数
     * 2.
     */
    public static void sort(int[] arr){
        sort(arr,0,arr.length-1);
    }

    /**
     * 将数组分成左右两半，左边是left-mid，右边是mid+1-right
     * 递归将左边和右边的数组分别进行排序，然后将左右两边有序数组合并成为一个大的有序数组
     * 分治递归的**是：如果左边和右边都只有一个元素，那么就可以认为左边和右边都是有序数组，然后直接合并即可
     * @param arr
     * @param left
     * @param right
     */
    private static void sort(int[] arr,int left,int right){
        //如果元素的个数只有一个，那么认为是有序的
        if(left == right){
            return;
        }
        int mid = (left+right)/2;
        //排序左半部分
        sort(arr,left,mid);
        //排序右半部分
        sort(arr,mid+1,right);
        //左边和右边有序了之后，将左右两边的数组进行合并
        merge(arr,left,mid,right);
    }

    private static void merge(int[] arr,int left,int mid,int right){
        //定一个存储左右两边元素的临时数组
        int[] temp = new int[right-left+1];
        int temp_index = 0;
        //将左边和右边的数组中的有序元素合并到临时数组中
        int temp_left = left;
        int temp_right = mid+1;
        //只要左侧和右侧数组都还有元素，那么就比较两个元素，并且将小的放在临时数组中
        while (temp_left<=mid && temp_right<=right){
            if(arr[temp_left]<arr[temp_right]){
                temp[temp_index++] = arr[temp_left++];
            }else{
                temp[temp_index++] = arr[temp_right++];
            }
        }
        //上方循环完成后，则左侧或右侧数组有一个数组已经空了，则将另外一个非空的数组循环放入到临时数组中
        while (temp_left<=mid){
            temp[temp_index++] = arr[temp_left++];
        }
        while (temp_right<=right){
            temp[temp_index++] = arr[temp_right++];
        }
        //最终临时数组中是有序的数组，则顺序将临时数组中的元素放置在arr中的left到right的位置
        for(int i=0;i<temp_index;i++){
            arr[left+i] = temp[i];
        }
    }
}

public class MyMergeV2 {
    private static int[] tempArr;

    public static void sort(int[] arr) {
        tempArr = new int[arr.length];
        sort(arr, 0, arr.length - 1);
    }

    /**
     * 将给定left-right长度的数组分成左边有右边两个数组，并且递归将其排好序后，合并成为一个有序数组
     * @param arr
     * @param left
     * @param right
     */
    private static void sort(int[] arr, int left, int right) {
        //如果left==right，则认为该数组的长度只有1，则已经为有序数组
        if(left == right){
            return;
        }
        int mid = (left+right)/2;
        sort(arr,left,mid);
        sort(arr,mid+1,right);
        if(arr[mid]>arr[mid+1]){
            //****优化：只有左侧数组最后一个元素大于右侧第一个元素，才认为需要进行合并操作，否则left-right数组本身就是有序，无需进行合并操作
            merge(arr,left,mid,right);
        }
    }

    /**
     * 将左侧有序的数组以及右侧有序的数组合并成为一个大的有序数组
     * @param arr
     * @param left
     * @param mid
     * @param right
     */
    private static void merge(int[] arr,int left,int mid,int right){
        //只要左右两个数组都还没有被遍历完，则始终对比左侧和右侧数组最左侧的元素，将最小的数据推到队列中
        int temp_left = left;
        int temp_right = mid+1;
        int temp_index = left;
        while (temp_left<=mid && temp_right<=right){
            //说明左右两个数组元素都不空
            if(arr[temp_left]<arr[temp_right]){
                //如果左边第一个元素小，则左边的放入临时数组中
                tempArr[temp_index++] = arr[temp_left++];
            }else{
                //如果右边元素小，则右边第一个元素放入临时数组中
                tempArr[temp_index++] = arr[temp_right++];
            }
        }
        //到此为止，则要么左侧元素已经遍历完成，要么右侧元素已经遍历完成，则只剩下一个非空的数组，将未遍历到的剩余数据依次放入到临时数组中
        while (temp_left<=mid){
            //则左侧数组非空
            tempArr[temp_index++] = arr[temp_left++];
        }
        while (temp_right<=right){
            //则右侧数组非空
            tempArr[temp_index++] = arr[temp_right++];
        }
        //将合并后有序的临时数组中的元素依次重新放入到原数组中
        for(int i=left;i<=right;i++){
            arr[i] = tempArr[i];
        }
    }
}

public class MyFastSort {
    public static void sort(int[] arr){
        sort(arr,0,arr.length-1);
    }

    private static void sort(int[] arr,int left,int right){
        //如果left==right，则说明需要排序的只有一个元素，则默认有序，也是递归的边界条件
        if(left >= right){
            return;
        }
        int index = sharding(arr,left,right);
        //递归将分界点左侧和右侧的数据进行排序
        sort(arr,left,index);
        sort(arr,index+1,right);
    }

    /**
     * 对arr[left-right]的元素进行切分，主要**是拿第一个元素作为边界，然后从第二个元素向后推，同时最后一个元素向前推，
     * 将左边比第一个元素大的与右边比第一个元素小的进行交换，直到相遇，那么相遇的位置就是第一个元素的位置，并且将第一个元素交换到该位置
     * @param arr
     * @param left
     * @param right
     * @return
     */
    private static int sharding(int[] arr, int left, int right) {
        int index = left;
        //确定基准元素
        int val = arr[left];
        //确定最左边的指针和最右边的指针，即left+1和right，只要两个指针没有相遇，那么就从从两头向中间推进，
        int temp_left = left+1;
        int temp_right = right;
        while (temp_left<temp_right){
            //先从左边开始向右找到第一个比var大的元素，即只要还在范围内并且left元素小于val，则向右推进
            while (arr[temp_left]<=val && temp_left<temp_right){
                temp_left++;
            }
            while (arr[temp_right]>=val && temp_left<temp_right){
                temp_right--;
            }
            //如果此时相遇，则说明左侧元素都小于val，右侧元素都大于val，那么如果val大于相遇的位置，则放在右边，否则放在左边
            if(temp_left==temp_right){
                if(arr[temp_left]<val){
                    //temp_left小于基准值，则交换temp_left与val的位置
                    U.swap(arr,left,temp_left);
                    index = temp_left;
                }else{
                    //否则说明temp_left的元素比val大，交换temp_left-1与val的位置
                    U.swap(arr,left,temp_left-1);
                    index = temp_left-1;
                }
            }else{
                //否则，则说明左边有比val大的元素，右侧有比val小的元素，则交换两者位置
                U.swap(arr,temp_left,temp_right);
            }
        }
        return index;
    }
}

public class FastSort {
    public static void sort(int[] arr) {
        sort(arr, 0, arr.length - 1);
    }

    private static void sort(int[] arr, int left, int right) {
        if (right <= left) {
            return;
        }
        int j = partition(arr, left, right); // 切分（请见“快速排序的切分”）
        sort(arr, left, j - 1); // 将左半部分a[lo .. j-1]排序
        sort(arr, j + 1, right); // 将右半部分a[j+1 .. hi]排序
    }

    private static int partition(int[] arr, int left, int right) { // 将数组切分为a[lo..i-1], a[i], a[i+1..hi]
        int i = left, j = right + 1; // 左右扫描指针
        int v = arr[left]; // 切分元素
        while (true) { // 扫描左右，检查扫描是否结束并交换元素
            while (arr[++i] < v) {
                if (i == right) {
                    break;
                }
            }
            while (v < arr[--j]) {
                if (j == left) {
                    break;
                }
            }
            if (i >= j) {
                break;
            }
            U.swap(arr, i, j);
        }
        U.swap(arr, left, j);// 将v = a[j]放入正确的位置
        return j; // a[lo..j-1] <= a[j] <= a[j+1..hi] 达成
    }
}

public class BinarySearchTreeBook<K extends Comparable<K>, V> {

    private Node root;

    /**
     * 获取二叉树的节点个数
     *
     * @return
     */
    public int size() {
        return size(root);
    }

    private int size(Node node) {
        if (null == node) {
            return 0;
        }
        return node.N;
    }

    /**
     * 获取指定k的value值
     *
     * @param k
     * @return
     */
    public V get(K k) {
        return get(root, k);
    }

    private V get(Node node, K k) {
        if (node == null) {
            return null;
        }
        if (node.key.equals(k)) {
            return node.value;
        }
        if (U.less(node.key, k)) {
            //比当前节点大，向右查询
            return get(node.right, k);
        } else {
            //否则比当前节点小，向左查询
            return get(node.left, k);
        }
    }

    /**
     * 向二叉树中存入新的节点，如果存在相同的k，则替换v
     *
     * @param k
     * @param v
     */
    public void put(K k, V v) {
        root = put(root, k, v);
    }

    private Node put(Node node, K k, V v) {
        if (null == node) {
            return new Node(k, v, 1);
        }
        if (node.key.equals(k)) {
            node.value = v;
        } else if (U.less(node.key, k)) {
            //k大于当前节点的key，放在右侧
            node.right = put(node.right, k, v);
        } else {
            //k小于当前节点的key，放在左侧
            node.left = put(node.left, k, v);
        }
        node.N = size(node.left) + size(node.right);
        return node;
    }

    /**
     * 获取最小的k，也就是获取最左侧节点的key
     *
     * @return
     */
    public K min() {
        if (null == root) {
            return null;
        }
        return min(root).key;
    }

    private Node min(Node node) {
        if (null == node) {
            return null;
        }
        if (null == node.left) {
            return node;
        } else {
            return node.left;
        }
    }

    /**
     * 获取当前树中的最大元素
     * @return
     */
    public K max(){
        if(null==root){
            return null;
        }
        return max(root).key;
    }

    private Node max(Node node){
        if(node.right==null){
            return node;
        }else{
            return max(node.right);
        }
    }

    /**
     * 获取小于等于k的最大元素
     *
     * @param k
     * @return
     */
    public K floor(K k) {
        Node node = floor(root, k);
        if (null != node) {
            return null;
        }
        return node.key;
    }

    private Node floor(Node node, K k) {
        if (null == node) {
            return null;
        }
        if (node.key.equals(k)) {
            return node;
        }
        if (!U.less(node.key, k)) {
            //k比node.key小，在左边，向左递归查找
            return floor(node.left, k);
        }
        //如果在右边，向右递归查询是否有小于k的节点，如果没有则当前节点是小于k的最大节点
        Node floor = floor(node.right, k);
        if (null == floor) {
            return node;
        } else {
            return floor;
        }
    }

    /**
     * 返回排名为k的节点
     *
     * @param k
     * @return
     */
    public K select(int k) {
        Node node = select(root, k);
        return null != node ? node.key : null;
    }

    private Node select(Node node, int k) {
        if (null == node) {
            return null;
        }
        int t = size(node.left);
        if (t == k) {
            return node;
        } else if (t > k) {
            //在左边
            return select(node.left, k);
        } else {
            //在右边
            return select(node.right, k - t - 1);
        }
    }

    /**
     * 返回以x为根结点的子树中小于x.key的键的数量
     *
     * @param k
     * @return
     */
    public int rank(K k) {
        return rank(root, k);
    }

    private int rank(Node node, K k) {
        if (node == null) {
            return 0;
        }
        if (node.key.equals(k)) {
            return size(node.left);
        }
        if (U.less(node.key, k)) {
            //比当前节点大，则向右找再加上左子树的数量
            return size(node) + rank(node.right, k);
        } else {
            //比当前节点小，则向左找
            return rank(node.left, k);
        }
    }

    /**
     * 删除最小的元素
     * 思路是：从左向下递归查询，直到某个节点的左子树为空，那么该节点就是最小的元素
     * 如果该节点的右节点为空，那么就直接将他的父节点的left指向空即可
     * 如果该节点的右节点非空，那个根据二叉树的添加规则说明他的右节点肯定小于他的父节点，否则就会在添加时被添加到他父节点的右边，所以直接将其父节点的left指向要删除节点的right
     *
     * @return
     */
    public void delMin() {
        root = delMin(root);
    }

    private Node delMin(Node node) {
        //如果left是空，那么直接返回该节点的右节点
        if (node.left == null) {
            return node.right;
        }
        //否则递归的向左查找
        node.left = delMin(node.left);
        node.N = size(node.left) + size(node.right) + 1;
        return node;
    }

    /**
     * 删除最大元素
     * 思路是：逐步向右下查找，直到找到右节点为空的节点，那么认为该节点最大，则将该节点的父节点指向他的左节点，即没有元素指向他，完成删除最大元素
     */
    public void delMax() {
        root = delMax(root);
    }

    private Node delMax(Node node) {
        if (node.right == null) {
            //如果右侧节点为空，则说明当前元素最大，将其父节点右侧指向他的左节点
            return node.left;
        }
        node.right = delMin(node);
        node.N = size(node.left) + size(node.right) + 1;
        return node;
    }

    /**
     * 删除指定元素，思路：
     * 1.找到指定要删除的元素k
     * 2.如果k无左子树，则直接return k的右子树
     * 3.如果k有左子树，无右子树，则直接return k的左子树
     * 4.如果k既有左子树，也有右子树，则删除并取出右子树中的最小节点min，将k节点父节点left指向min，将min的左子树指向k的左子树，将min的右子树指向k的右子树
     * 备注：实际上如果要删除的节点有左子树或右子树，实际上就是把左子树中最大的或者右子树中最小的拿出来替换当前要删除元素的位置
     *
     * @param k
     */
    public void delete(K k) {
        root = delete(root, k);
    }

    private Node delete(Node node, K k) {
        if (node == null) {
            return null;
        }
        if (node.key.equals(k)) {
            //如果当前元素是要删除的元素
            if(node.left==null){
                //左边为空
                return node.right;
            }else if(node.right==null){
                //左边不为空，但右边为空
                return node.left;
            }else{
                //左边不为空，右边也不为空
                //删除并获取右子树中最小的元素
                Node rightMin = delMin(node.right);
                //该元素左边指向要删除节点的左子树
                rightMin.left = node.left;
                //该元素右边指向要删除节点的右子树
                rightMin.right = node.right;
                return rightMin;
            }
        }
        //当前元素不是要删除的元素，则根据大小继续向右或向左查找
        if (U.less(node.key, k)) {
            //如果k比当前节点的key大，则向右查找
            return delete(node.right, k);
        } else {
            return delete(node.left, k);
        }
    }

    /**
     * 遍历二叉树：按照从小到大的方式遍历
     */
    public void printLeft(){
        printLeft(root);
    }

    private void printLeft(Node node){
        //如果左边有，那先输出左边
        if(node.left!=null){
            printLeft(node.left);
        }
        //遍历完左边后，打印当前节点
        System.out.print(""+node.key+"--"+node.value+"\t");
        //打印完中间后，打印右子树
        if(null!=node.right){
            printLeft(node.right);
        }
    }

    /**
     * 提供遍历方法
     * @return
     */
    public Iterable<K> iterator(){
        return iterator(min(),max());
    }

    /**
     * 遍历指定范围的树
     * @param min
     * @param max
     * @return
     */
    public Iterable<K> iterator(K min,K max){
        Queue<K> queue = new LinkedList<>();
        keys(root,min,max,queue);
        return queue;
    }

    /**
     * 将树中的所有在min和max范围内的节点key放在queue中
     * @param node
     * @param min
     * @param max
     * @param queue
     */
    private void keys(Node node,K min,K max,Queue<K> queue){
        if(null==node){
            return;
        }
        if(U.less(min,node.key) && U.less(node.key,max)){
            queue.offer(node.key);
        }
        keys(node.left,min,max,queue);
        keys(node.right,min,max,queue);
    }

    /**
     * 二叉树的内部数据结构
     */
    private class Node {
        private K key;
        private V value;
        private Node left, right;
        private int N;

        public Node(K key, V value, int n) {
            this.key = key;
            this.value = value;
            N = n;
        }
    }
}