桶排序

计数排序

解题思路
1、取出数组中的最大值。
2、以（最大值 +1）作为辅助数组大小进行记录数组信息。
3、重新把辅助数组中的数据转回数组中。

Java代码

public void countSort(int[] arr) {
    // 设置最大值变量并找出
    int max = arr[0];
    for (int i = 1; i < arr.length; i++) {
        if (max < arr[i]) {
            max = arr[i];
        }
    }
    // 设置辅助数组
    int[] tmp = new int[max+1];
    // 将数据保存到辅助数组中
    for (int i = 0; i < arr.length; i++) {
        tmp[arr[i]]++;
    }
    // 从辅助数组中数据转到数组中
    int index = 0;
    for (int i = 0; i < tmp.length; ) {
        if (tmp[i] == 0) {
            i++;
        } else {
            arr[index] = i;
            tmp[i]--;
            index++;
        }
    }
}

基数排序

解题思路
1、先对数的个位数进行排序（放到10个桶中0-9）
2、将排好的数据重新放回原数组中
3、再对数的下一个位数进行排序（同理1）
4、全部位数排序后就ok了

Java代码

public class RadixSort {

    public static void main(String[] args) {
        int[] array = {0,2,11,3,1,5,9,8,7};
        new RadixSort().radixSort(array);

        System.out.println(Arrays.toString(array));
    }

    public void radixSort(int[] array) {
        int max = getMax(array);
        int bit = 1;
        while(max / bit > 0) {
            radix(array, bit);
            bit *= 10;
        }
    }

    private void radix(int[] array, int bit) {
        // 用来装对应位数数据
        int[][] tmp = new int[10][array.length];
        // 用于保存位数个数
        int[] tmpIndex = new int[10];
        // 进行位数排序
        for (int i = 0; i < array.length; i++) {
            int num =(array[i] / bit) % 10;
            tmp[num][tmpIndex[num]] = array[i];
            tmpIndex[num]++;
        }

        // 将位数排序重新赋值回原数组
        int arrayIndex = 0;
        for (int i = 0; i < tmp.length; i++) {
            for (int j = 0; j < tmpIndex[i]; j++) {
                array[arrayIndex++] = tmp[i][j];
            }
        }
    }

    private int getMax(int[] array) {
        int max = array[0];
        for(int i = 1; i < array.length; i++){
            if(array[i] > max) {
                max = array[i];
            }
        }
        return max;
    }

}

桶排序

解题思路

1、先将数组划分成几个桶
2、将数组中的数据放到对应的桶中
3、对桶中的数据进行排序
4、将桶中的数组进行合并到原数组上

计算放在哪个桶：(arr[i]- min) / ((max-min) / (bucketNum - 1));

Java代码

public class BucketSort {

    public static void main(String[] args) {
        double[] arr = {0.1,0.6,0.3,0.9,0.2};
        new BucketSort().bucketSort(arr, 6);
        System.out.println(Arrays.toString(arr));
    }

    /**
     * [0,1)之间的数进行排序
     * @param arr 数组
     * @param bucketSize 桶大小
     */
    private void bucketSort(double[] arr, int bucketSize) {
        List<Double>[] bucket = new ArrayList[bucketSize];
        for (int i = 0; i < bucketSize; i++) {
            bucket[i] = new ArrayList<>();
        }

        for (int i = 0; i < arr.length; i++) {
            int num = (int) Math.floor(bucketSize * arr[i]);
            bucket[num].add(Double.valueOf(arr[i]));
        }
        int arrIndex = 0;
        for (int i = 0; i < bucketSize; i++) {
            Collections.sort(bucket[i]);
            for (int j = 0; j < bucket[i].size(); j++) {
                arr[arrIndex++] = bucket[i].get(j);
            }
        }
    }
}