【JAVA数据结构】其他排序（了解即可）

/**
     * 在稀疏情况下，范围有可能会远大于N ,导致速度极慢空间极大
     * 计数排序，有局限性（必须知道bound限制,或者的自己算）
     * 没有发生交换(除了在获取最大最小值得时候)
     * 时间复杂度 O( max (范围, N))  //可能很稀疏就浪费很多空间了
     * 空间复杂度 O(范围)额外空间
     * @param arr
     * @param bound
     */
//这种是提供范围参数的方法
    public static void countSort(int[] arr, int start, int bound) {
        arr = Arrays.copyOf(arr, arr.length);
        int[] count = new int[bound - start];
        for(int x : arr) {
            count[x - start]++;
        }
        int j = 0;
        for (int i = 0; i <= bound - start - 1; ) {
            while(count[i] == 0) {
                i++;
                if(i > bound - start - 1) {
                    break;
                }
            }
            if(j > arr.length - 1 || i > bound - start - 1) {
                break;
            }
            arr[j++] = i + start;
            count[i]--;
        }
    }
//这是不提供范围，自身自动查找范围的方法
    public static void countSort(int[] arr) {
        int min = arr[0];
        int max = arr[0];
        for (int x : arr) {
            if (max < x) {
                max = x;
            }
            if (min > x) {
                min = x;
            }
        }
        arr = Arrays.copyOf(arr, arr.length);
        int[] count = new int[max - min + 1];
        for (int x : arr) {
            count[x - min]++;
        }
        int j = 0;
        for (int i = 0; i <= max - min; ) {
            while(count[i] == 0) {
                i++;
                if (i > max - min) {
                    break;
                }
            }
            if (j > arr.length - 1 || i > max - min) {
                break;
            }
            arr[j++] = i + min;
            count[i]--;
        }
    }

/**
 * 基数排序---->可以不交换不比较
 * 并且！只能用于整形家族
 * 时间 O(N*lgN)
 * 空间 O(N)
 * @param arr
 */
public static void  cardinalSort(int[] arr) {
    arr = Arrays.copyOf(arr, arr.length);
    List<Queue<Integer>> queueList = new ArrayList<>();
    for (int i = 0; i < 20; i++) {
        queueList.add(new LinkedList<>());
    }
    int x = 1;
    int y = 10;
    while(true) {
        for (int i = 0; i < arr.length; i++) {
            int tmp = arr[i] % y / x;
            queueList.get(tmp + 9).offer(arr[i]);
        }
        if(queueList.get(9).size() == arr.length) {
            break;
        }
        int j = 0;
        for (int i = 0; i < 20; i++) {
            while(!queueList.get(i).isEmpty()) {
                arr[j++] = queueList.get(i).poll();
            }
        }
        x *= 10;
        y *= 10;
    }
}

/**
     * 桶排序
     * 思想很简单，只需要分组分别排序即可（哈希思想）
     * 但是需要有一个基础的排序法（也可以结合递归，那样更慢了，原理还不如放在搜索数之中，然后直接中序遍历，或者快速排序）
     * 稳定不稳定取决于二级排序方法是什么
     * 这种方法是强制有规律的分割！并不能在原数组进行”本质“修改，跟计数排序差不多
     * @param arr
     */
    private static final int BUCKET_CAPACITY = 500;//一个桶的范围
    public static void bucketSort(int[] arr) {
        arr = Arrays.copyOf(arr, arr.length);
        //桶的个数
        int[] tmp = Arrays.copyOf(arr, arr.length);
        int min = tmp[0];
        int max = tmp[0];
        for(int x : tmp) {
            if(min > x) {
                min = x;
            }
            if(max < x) {
                max = x;
            }
        }
        int number = (max - min + 1) / BUCKET_CAPACITY + 1;
        int[] count = new int[number];
        List<List<Integer>> list = new ArrayList<>();
        for (int i = 0; i < number; i++) {
            list.add(new ArrayList<>());
        }
        for (int i = 0; i < tmp.length; i++) {
            int index = (tmp[i] - min) / BUCKET_CAPACITY;
            list.get(index).add(tmp[i]);
        }
        for (int i = 0; i < number; i++) {
            Collections.sort(list.get(i));
        }
        int size = 0;
        for (int i = 0; i < number; i++) {
            for (int j = 0; j < list.get(i).size(); j++) {
                arr[size++] = list.get(i).get(j);
            }
        }
    }

public class BinarySearchTree {
    static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(int val) {
            this.val = val;
        }
    }
    public TreeNode root;
    //普通搜索二叉树，时间复杂度是O(N)最差【单分支】，O(log2N)最优【完全二叉树】
    public void insert(int val) {
        if(root == null) {
            root = new TreeNode(val);
            return;
        }
        TreeNode cur = root;
        TreeNode prev = null;
        while(cur != null) {
            prev = cur;
            if(val <= cur.val) {
                cur = cur.left;
            }else {
                cur = cur.right;
            }
        }if(val <= prev.val) {
            prev.left = new TreeNode(val);
        }else {
            prev.right = new TreeNode(val);
        }
    }
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root != null) {
            list.addAll(inorderTraversal(root.left));
            list.add(root.val);
            list.addAll(inorderTraversal(root.right));
        }
        return list;  
    }
}

/**
     * 搜索树排序
     * 稳定
     * @param arr
     */
    public static void binarySearchTreeSort(int[] arr) {
        arr = Arrays.copyOf(arr, arr.length);
        BinarySearchTree tree = new BinarySearchTree();
        for(int x : arr) {
            tree.insert(x);
        }
        List<Integer> list = tree.inorderTraversal(tree.root);
        int i = 0;
        for(Integer x : list) {
            arr[i++] = x;
        }
    }