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

public class BucketSort {
    
    /**
     * 桶排序（适用于 [0, 1) 区间内的浮点数）
     */
    public static void sort(double[] arr) {
        int n = arr.length;
        if (n <= 1) return;
        
        // 创建 n 个桶
        @SuppressWarnings("unchecked")
        List<Double>[] buckets = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            buckets[i] = new ArrayList<>();
        }
        
        // 将元素分配到桶中
        for (double value : arr) {
            int bucketIndex = (int) (value * n);
            if (bucketIndex >= n) bucketIndex = n - 1;  // 处理边界情况
            buckets[bucketIndex].add(value);
        }
        
        // 对每个桶进行排序
        for (List<Double> bucket : buckets) {
            Collections.sort(bucket);
        }
        
        // 合并所有桶
        int index = 0;
        for (List<Double> bucket : buckets) {
            for (double value : bucket) {
                arr[index++] = value;
            }
        }
    }
    
    /**
     * 桶排序（适用于整数，指定范围）
     * @param arr 待排序数组
     * @param minValue 数组中的最小值
     * @param maxValue 数组中的最大值
     * @param bucketCount 桶的数量
     */
    public static void sortIntegers(int[] arr, int minValue, int maxValue, int bucketCount) {
        if (arr.length <= 1) return;
        
        // 创建桶
        @SuppressWarnings("unchecked")
        List<Integer>[] buckets = new ArrayList[bucketCount];
        for (int i = 0; i < bucketCount; i++) {
            buckets[i] = new ArrayList<>();
        }
        
        // 计算桶的范围
        double range = (double) (maxValue - minValue + 1) / bucketCount;
        
        // 分配到桶
        for (int value : arr) {
            int bucketIndex = (int) ((value - minValue) / range);
            if (bucketIndex >= bucketCount) bucketIndex = bucketCount - 1;
            buckets[bucketIndex].add(value);
        }
        
        // 对每个桶进行排序
        for (List<Integer> bucket : buckets) {
            Collections.sort(bucket);
        }
        
        // 合并
        int index = 0;
        for (List<Integer> bucket : buckets) {
            for (int value : bucket) {
                arr[index++] = value;
            }
        }
    }
    
    /**
     * 桶排序（泛型版本，使用自然排序）
     */
    public static <T extends Comparable<T>> void sortGeneric(T[] arr, int bucketCount) {
        if (arr.length <= 1) return;
        
        // 找到最小值和最大值
        T min = arr[0], max = arr[0];
        for (T value : arr) {
            if (value.compareTo(min) < 0) min = value;
            if (value.compareTo(max) > 0) max = value;
        }
        
        // 创建桶
        @SuppressWarnings("unchecked")
        List<T>[] buckets = new ArrayList[bucketCount];
        for (int i = 0; i < bucketCount; i++) {
            buckets[i] = new ArrayList<>();
        }
        
        // 分配到桶
        for (T value : arr) {
            int bucketIndex = getBucketIndex(value, min, max, bucketCount);
            buckets[bucketIndex].add(value);
        }
        
        // 排序每个桶
        for (List<T> bucket : buckets) {
            Collections.sort(bucket);
        }
        
        // 合并
        int index = 0;
        for (List<T> bucket : buckets) {
            for (T value : bucket) {
                arr[index++] = value;
            }
        }
    }
    
    private static <T extends Comparable<T>> int getBucketIndex(T value, T min, T max, int bucketCount) {
        // 使用 double 进行比例计算
        double ratio = (double) (value.compareTo(min)) / (max.compareTo(min) + 1);
        int index = (int) (ratio * bucketCount);
        if (index >= bucketCount) index = bucketCount - 1;
        return index;
    }
}