简单排序--桶排序，计数排序，基数排序

简单排序

这几种排序都是O(n)的时间复杂度，都是基于非比较的，不涉及到元素之间的比较操作

桶排序

将排序的数量n,均匀划分到m个桶内，那么每个桶就有k = n /m个，桶内使用快排那么时间复杂度就是 O(k * logk) -> 当n / m 趋近于1 那么复杂度趋近于O(n)
桶排序适用于外部排序，适用于有大量数据的情况

private void bucketSort(int[] arr){
        int max = arr[0];
        int min = arr[0];
        for (int item : arr) {
            max = Math.max(max, item);
            min = Math.min(min, item);
        }
        // 数值的范围
        int temp = max - min;
        int bucketLength = arr.length;
        List<LinkedList<Integer>> bucket = new LinkedList<>(bucketLength);
        for (int i = 0 ; i < bucketLength;i++){
            bucket.add(new LinkedList<>());
        }

        for (int value : arr) {
            int num = (value - min) / (temp / (bucketLength - 1));
            bucket.get(num).add(value);
        }

        for (int i = 0 ; i < bucketLength; i++){
            LinkedList<Integer> integers = bucket.get(i);
            // 快排
        }

        // 每个桶内的数据已经排序完成，拼接起来即可

计数排序

也相当于桶排序，只是一种特殊的桶排序，每个桶里，只有一个数据,省去了桶内排序的过程，适用于数据量很少

        private int[] countSort(int[] arr){

        //计数的范围 最大--最小
        int max = arr[0];
        int min = arr[0];
        for (int value : arr) {
            if (max < value) {
                max = value;
            }
            if (min > value) {
                min = value;
            }
        }

        int distance = max - min ;
        int[] countArray = new int[distance + 1];
        for (int value : arr) {
            countArray[value - min]++;
        }
        int sum = 0;
        for (int i = 0; i < countArray.length; i++) {
            sum += countArray[i];
            countArray[i] = sum;
        }
        int[] sortArray  = new int[arr.length];
        for (int i = arr.length - 1; i >= 0 ; i--) {
            sortArray[countArray[arr[i] -min] - 1] = arr[i];
            countArray[arr[i] - min ] --;
        }
        return sortArray;
    }

基数排序

相当于按位比较，比较完后，将对应的数据返回，O(n)稳定

/**
     *
     * @param arr 数组
     * @param maxPosition 最高位
     */
    private void redixSort(int[] arr,int max){
        //count数组用来计数
        int[] count = new int[10];
        //bucket用来当桶（在下面你就理解了什么是桶了），放数据，取数据
        int[] bucket = new int[arr.length];

        //k表示第几位，1代表个位，2代表十位，3代表百位
        for(int k=1;k<=max;k++)
        {
            //把count置空，防止上次循环的数据影响
            for(int i=0;i<arr.length;i++)
            {
                count[i] = 0;
            }

            //分别统计第k位是0,1,2,3,4,5,6,7,8,9的数量
            //以下便称为桶
            //即此循环用来统计每个桶中的数据的数量
            for(int i=0;i<arr.length;i++)
            {
                count[getFigure(arr[i],k)]++;
            }

            //利用count[i]来确定放置数据的位置
            for(int i=1;i<arr.length;i++)
            {
                count[i] = count[i] + count[i-1];
            }
            //执行完此循环之后的count[i]就是第i个桶右边界的位置

            //利用循环把数据装入各个桶中，注意是从后往前装
            //这里是重点，一定要仔细理解
            for(int i=arr.length-1;i>=0;i--)
            {
                int j = getFigure(arr[i],k);
                bucket[count[j]-1] = arr[i];
                count[j]--;
            }

            //将桶中的数据取出来，赋值给arr
            for(int i=0,j=0;i<arr.length;i++,j++)
            {
                arr[i] = bucket[j];
            }

        }
    }

    public static int getFigure(int i,int k)
    {
        int[] a = {1,10,100};
        return (i/a[k-1])%10;
    }