【重温基础算法】内部排序之桶排序法

内部排序之桶排序法

桶排序是计数排序的升级版，主要将它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：

1. 在额外空间充足的情况下，尽量增大桶的数量
2. 使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中

同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。

主要思想

1. 准备K个桶，对桶进行编号
2. 遍历待排序系列，将元素放到合理的桶中
3. 对每个桶内的元素进行桶内排序
4. 从第一个桶开始，依次从桶内获取元素，最终形成的序列就是排序完成的序列

过程演示

java实现

package sort;

import java.util.Arrays;

public class BucketSort {
    public static void main(String[] args) {
        int[] o = {7, 6, 15, 3, 16, 5, 2, 4, 8};
        System.out.print("排序前: ");
        for (int t : o) {
            System.out.print(t);
            System.out.print(" ");
        }
        System.out.println();

        // 算法部分
        // 计算桶的个数，桶的个数多少合适呢？
        int maxValue = o[0];
        int minValue = o[0];
        for (int v : o) {
            if (v  maxValue) {
                maxValue = v;
            }
        }
        // 待排数组中的最大最小差值/单个桶的元素最大个数后再加1
        int bucketCount = (maxValue - minValue) / o.length + 1;
        System.out.println("桶的个数: " + bucketCount);
        int[][] buckets = new int[bucketCount][0];

        for (int j : o) {
            // 计算元素该在哪个桶里/单个桶的元素最大个数
            int index = (j - minValue) / o.length;
            buckets[index] = arrAppend(buckets[index], j);
        }

        int arrIndex = 0;
        // 依次遍历桶
        int count = 1;
        for (int[] bucket : buckets) {
            // 排除空桶
            if (bucket.length