排序算法之桶排序

一、简介

稳定：如果A原本在B前面，而A=B，排序之后A仍然在B的前面；
不稳定：如果A原本在B的前面，而A=B，排序之后A可能会出现在B的后面；
时间复杂度： 描述一个算法执行所耗费的时间；
空间复杂度：描述一个算法执行所需内存的大小；
n：数据规模；
k：“桶”的个数；
In-place：占用常数内存，不占用额外内存；
Out-place：占用额外内存。

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

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

同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。
什么时候最快?
当输入的数据可以均匀的分配到每一个桶中。
什么时候最慢?
当输入的数据被分配到了同一个桶中。

算法步驟：

• 1.确定桶的数量：根据输入数据的范围和数量确定需要多少个桶。
  首先确定桶的个数。因为桶排序最好是将数据均匀地分散在各个桶中，那么桶的个数最好是应该根据数据的分散情况来确定。首先找出所有数据中的最大值mx和最小值mn；
  根据mx和mn确定每个桶所装的数据的范围 size，有
  size = (mx - mn) / n + 1，n为数据的个数，需要保证至少有一个桶，故而需要加个1；
  求得了size即知道了每个桶所装数据的范围，还需要计算出所需的桶的个数cnt，有
  cnt = (mx - mn) / size + 1，需要保证每个桶至少要能装1个数，故而需要加个1；
• 2.将数据分配到各个桶中：遍历输入数据，根据数据的值将数据分配到对应的桶中。
  求得了size和cnt后，即可知第一个桶装的数据范围为 [mn, mn + size)，第二个桶为 [mn + size, mn + 2 * size)，…，以此类推，因此步骤2中需要再扫描一遍数组，将待排序的各个数放进对应的桶中。
• 3.对每个桶内的数据进行排序：对每个非空的桶内的数据进行排序，可以使用插入排序等方法。
• 4.合并各个桶的数据：按照桶的顺序将各个桶内的数据合并为最终的排序结果。

示意图
元素分布在桶中：

然后，元素在每个桶中排序：

二、代码实现

 public void bucketSort(int[] nums) {
        int n = nums.length;
        int mn = nums[0], mx = nums[0];
        // 找出数组中的最大最小值
        for (int i = 1; i < n; i++) {
            mn = Math.min(mn, nums[i]);
            mx = Math.max(mx, nums[i]);
        }
        int size = (mx - mn) / n + 1; // 每个桶存储数的范围大小，使得数尽量均匀地分布在各个桶中，保证最少存储一个
        int cnt = (mx - mn) / size + 1; // 桶的个数，保证桶的个数至少为1
        List<Integer>[] buckets = new List[cnt]; // 声明cnt个桶
        for (int i = 0; i < cnt; i++) {
            buckets[i] = new ArrayList<>();//每一个桶都是一个集合
        }
        // 扫描一遍数组，将数放进桶里
        for (int i = 0; i < n; i++) {
            int idx = (nums[i] - mn) / size;
            buckets[idx].add(nums[i]);
        }
        // 对各个桶中的数进行排序，这里用库函数快速排序
        for (int i = 0; i < cnt; i++) {
            buckets[i].sort(null); // 默认是按从小打到排序
        }
        // 依次将各个桶中的数据放入返回数组中
        int index = 0;
        for (int i = 0; i < cnt; i++) {
            for (int j = 0; j < buckets[i].size(); j++) {
                nums[index++] = buckets[i].get(j);
            }
        }
    }

demo示例一下

public class BucketSort {
    public static void bucketSort(int[] nums) {
        int n = nums.length;
        int mn = nums[0], mx = nums[0];
        // 找出数组中的最大最小值
        for (int i = 1; i < n; i++) {
            mn = Math.min(mn, nums[i]);
            mx = Math.max(mx, nums[i]);
        }
        int size = (mx - mn) / n + 1; // 每个桶存储数的范围大小，使得数尽量均匀地分布在各个桶中，保证最少存储一个
        System.out.println("每个桶的储存数量大小 " + size);
        int cnt = (mx - mn) / size + 1; // 桶的个数，保证桶的个数至少为1
        System.out.println("桶的个数 " + cnt);
        List<Integer>[] buckets = new List[cnt]; // 声明cnt个桶
        for (int i = 0; i < cnt; i++) {
            buckets[i] = new ArrayList<>();//每一个桶都是一个集合
        }
        for (int i = 0; i < n; i++) {
            int number1 = mn + i * size;
            int number2 = mn + (i + 1) * size;
            System.out.println("第" + i + "个桶存理应存放数据范围 " + number1 + "----" + number2);
        }
        // 扫描一遍数组，将数放进桶里
        for (int i = 0; i < n; i++) {
            int idx = (nums[i] - mn) / size;
            buckets[idx].add(nums[i]);
            System.out.println("第" + idx + "个桶存放了" + nums[i]);
        }
        // 对各个桶中的数进行排序，这里用库函数快速排序
        for (int i = 0; i < cnt; i++) {
            buckets[i].sort(null); // 默认是按从小打到排序
        }
        // 依次将各个桶中的数据放入返回数组中
        int index = 0;
        for (int i = 0; i < cnt; i++) {
            for (int j = 0; j < buckets[i].size(); j++) {
                nums[index++] = buckets[i].get(j);
            }
        }
    }

    public static void bucketSort2(int[] nums) {
        int n = nums.length;
        int mn = nums[0], mx = nums[0];
        // 找出数组中的最大最小值
        for (int i = 1; i < n; i++) {
            mn = Math.min(mn, nums[i]);
            mx = Math.max(mx, nums[i]);
        }
        int size = (mx - mn) / n + 1; // 每个桶存储数的范围大小，使得数尽量均匀地分布在各个桶中，保证最少存储一个
        int cnt = (mx - mn) / size + 1; // 桶的个数，保证桶的个数至少为1
        List<Integer>[] buckets = new List[cnt]; // 声明cnt个桶
        for (int i = 0; i < cnt; i++) {
            buckets[i] = new ArrayList<>();
        }
        // 扫描一遍数组，将数放进桶里
        for (int i = 0; i < n; i++) {
            int idx = (nums[i] - mn) / size;
            buckets[idx].add(nums[i]);
        }
        // 对各个桶中的数进行排序，这里用库函数快速排序
        for (int i = 0; i < cnt; i++) {
            buckets[i].sort(new Comparator<Integer>() {
                @Override
                public int compare(Integer a, Integer b) {
                    return b - a; // 从大到小排序
                }
            });
        }
        // 依次将各个桶中的数据放入返回数组中
        int index = 0;
        for (int i = cnt - 1; i >= 0; i--) {
            for (int j = 0; j < buckets[i].size(); j++) {
                nums[index++] = buckets[i].get(j);
            }
        }
    }

    public static void main(String[] args) {
        int[] nums = {12, 11, 15, 50, 7, 65, 3, 99};
        System.out.println("排序前 ：" + Arrays.toString(nums));
        bucketSort(nums);
        System.out.println("桶排序从小到大排序后 ：" + Arrays.toString(nums));
        bucketSort2(nums);
        System.out.println("桶排序从大到小排序后 ：" + Arrays.toString(nums));
    }
}

三、应用场景

桶排序适用于数据量较大且分布较均匀的情况，可以在一定程度上提高排序的效率。

• 排序整数或浮点数： 桶排序适用于排序整数或浮点数，特别是在这些数的范围不是很大的情况下。通过将数分配到不同的桶中，可以在每个桶内使用其他排序算法（如插入排序、快速排序）来对桶内的数进行排序，最终将桶中的数合并得到有序序列。
• 均匀分布的数据： 如果输入数据是均匀分布的，即数据在不同的范围内基本均匀分布，那么桶排序的效果会很好。因为桶排序将数据分配到不同的桶中，可以保证数据在各个桶中基本均匀分布，从而减少排序的复杂度。
• 外部排序： 桶排序也适用于外部排序，即当数据量非常大，无法一次性加载到内存中进行排序时。在外部排序中，可以将数据分成若干块，每块数据可以加载到内存中进行桶排序，然后将排序后的数据写回磁盘，最终将所有块合并得到有序序列。
• 计数排序的扩展： 桶排序是计数排序的一种扩展，适用于更大范围的数据。当计数排序不适用于数据范围很大的情况时，桶排序可以更好地处理这种情况。

桶排序的关键点：

• 确定桶的数量和大小：在进行桶排序之前，需要确定桶的数量和大小。桶的数量可以根据待排序数据的范围来确定，而桶的大小可以根据数据的分布情况来选择。通常情况下，桶的数量可以取数据个数的平方根或者数据范围的大小。
• 数据分配到桶中：一旦确定了桶的数量和大小，接下来需要将待排序数据分配到对应的桶中。这通常涉及到计算每个数据在哪个桶内，可以根据数据的大小和桶的范围来确定。
• 对每个非空桶内的数据进行排序：在桶排序中，每个非空桶内的数据需要进行排序。这可以使用任意一种排序算法，如插入排序、快速排序等。在实际应用中，通常选择适合桶内数据规模的排序算法。
• 合并各个桶的数据：最后一步是将各个桶内的数据按照顺序合并为最终的排序结果。这通常涉及遍历所有桶，按照桶的顺序将数据合并起来。
• 处理边界情况：在实现桶排序时，需要考虑处理一些边界情况，例如空桶的情况、数据分布不均匀的情况等。这些情况可能会影响桶排序的性能和正确性。

参考链接：
十大经典排序算法（Java实现）