桶排序前缀和数组java实现

桶排序是一种非比较排序算法，它通过将元素分配到有限数量的桶中，然后对每个桶内的元素进行排序，最后将所有桶中的元素按照顺序合并。在Java中，我们可以使用前缀和（prefix sum）的概念来辅助实现桶排序。

前缀和数组在桶排序中用来存储每个桶中元素的累计值，这样在合并过程中可以快速找到指定元素应该放入的位置。以下是一个简单的Java实现：

import java.util.ArrayList;
import java.util.List;

public class BucketSortWithPrefixSum {
    public static void bucketSort(int[] arr) {
        // 首先计算每个元素在排序范围内的索引位置（即桶的索引）
        int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
        for (int num : arr) {
            min = Math.min(min, num);
            max = Math.max(max, num);
        }

        int bucketCount = (max - min + 1) * 10; // 假设最大值在100范围内，桶的数量是1000
        int[] prefixSum = new int[bucketCount + 1]; // 为溢出预留一个额外的桶

        // 计算前缀和
        for (int num : arr) {
            prefixSum[num - min]++;
        }
        for (int i = 1; i < prefixSum.length; i++) {
            prefixSum[i] += prefixSum[i - 1];
        }

        // 把元素放到对应的桶里，然后对每个桶进行排序
        List<List<Integer>> buckets = new ArrayList<>();
        for (int i = 0; i < bucketCount; i++) {
            buckets.add(new ArrayList<>());
        }
        for (int num : arr) {
            buckets.get(prefixSum[num - min] - 1).add(num);
            prefixSum[num - min]--;
        }

        // 对每个桶进行排序，这里假设桶中的元素已经是有序的
        for (List<Integer> bucket : buckets) {
            bucket.sort(null); // 使用默认的升序排序
        }

        // 合并所有桶
        int sortedIndex = 0;
        for (List<Integer> bucket : buckets) {
            for (int num : bucket) {
                arr[sortedIndex++] = num;
            }
        }
    }

    // 示例使用
    public static void main(String[] args) {
        int[] arr = {5, 9, 1, 7, 3, 6, 8, 2, 4};
        bucketSort(arr);
        // 输出排序后的数组
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}