09.桶排序

目录介绍

1.基本思想
2.排序过程
3.代码实现
4.如何优化
5.复杂度
6.使用场景

1.基本思想

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。

2.排序过程

为了使桶排序更加高效，我们需要做到这两点：
- 在额外空间充足的情况下，尽量增大桶的数量
- 使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中
同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。

3.代码实现

代码如下所示

private static final InsertSort insertSort = new InsertSort();

@Override
public int[] sort(int[] sourceArray) throws Exception {
    // 对 arr 进行拷贝，不改变参数内容
    int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
    return bucketSort(arr, 5);
}

private int[] bucketSort(int[] arr, int bucketSize) throws Exception {
    if (arr.length == 0) {
        return arr;
    }

    int minValue = arr[0];
    int maxValue = arr[0];
    for (int value : arr) {
        if (value < minValue) {
            minValue = value;
        } else if (value > maxValue) {
            maxValue = value;
        }
    }

    int bucketCount = (int) Math.floor((maxValue - minValue) / bucketSize) + 1;
    int[][] buckets = new int[bucketCount][0];

    // 利用映射函数将数据分配到各个桶中
    for (int i = 0; i < arr.length; i++) {
        int index = (int) Math.floor((arr[i] - minValue) / bucketSize);
        buckets[index] = arrAppend(buckets[index], arr[i]);
    }

    int arrIndex = 0;
    for (int[] bucket : buckets) {
        if (bucket.length <= 0) {
            continue;
        }
        // 对每个桶进行排序，这里使用了插入排序
        bucket = insertSort.sort(bucket);
        for (int value : bucket) {
            arr[arrIndex++] = value;
        }
    }

    return arr;
}

/**
 * 自动扩容，并保存数据
 *
 * @param arr
 * @param value
 */
private int[] arrAppend(int[] arr, int value) {
    arr = Arrays.copyOf(arr, arr.length + 1);
    arr[arr.length - 1] = value;
    return arr;
}


public interface IArraySort {
    /**
     * 对数组进行排序，并返回排序后的数组
     *
     * @param sourceArray
     * @return
     * @throws Exception
     */
    int[] sort(int[] sourceArray) throws Exception;

}


public class InsertSort implements IArraySort {

    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        // 从下标为1的元素开始选择合适的位置插入，因为下标为0的只有一个元素，默认是有序的
        for (int i = 1; i < arr.length; i++) {

            // 记录要插入的数据
            int tmp = arr[i];

            // 从已经排序的序列最右边的开始比较，找到比其小的数
            int j = i;
            while (j > 0 && tmp < arr[j - 1]) {
                arr[j] = arr[j - 1];
                j--;
            }

            // 存在比其小的数，插入
            if (j != i) {
                arr[j] = tmp;
            }

        }
        return arr;
    }
}

4.如何优化

1.什么时候最快
- 当输入的数据可以均匀的分配到每一个桶中。
2.什么时候最慢
- 当输入的数据被分配到了同一个桶中。