桶排序

import java.util.*;

@SuppressWarnings("unchecked") // 抑制泛型数组相关的未检查警告
public class BucketSort {
    
    // 1. 基本版桶排序（处理0-1区间的浮点数）
    public static void bucketSortBasic(double[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        
        int n = arr.length;
        // 创建n个桶，添加注解抑制警告
        List<Double>[] buckets = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            buckets[i] = new ArrayList<>();
        }
        
        // 将元素分配到桶中
        for (double num : arr) {
            int bucketIndex = (int) (num * n); // 映射函数：num * n
            buckets[bucketIndex].add(num);
        }
        
        // 对每个桶排序并合并结果
        int index = 0;
        for (List<Double> bucket : buckets) {
            if (!bucket.isEmpty()) {
                Collections.sort(bucket);
                for (double num : bucket) {
                    arr[index++] = num;
                }
            }
        }
    }
    
    // 2. 优化版1：处理整数的桶排序
    public static void bucketSortIntegers(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        
        // 找出最大值和最小值，确定桶的范围
        int min = arr[0], max = arr[0];
        for (int num : arr) {
            if (num < min) min = num;
            if (num > max) max = num;
        }
        
        // 计算桶的数量和每个桶的范围
        int bucketCount = (int) Math.sqrt(arr.length) + 1;
        int range = (max - min) / bucketCount + 1;
        
        // 创建桶
        List<Integer>[] buckets = new ArrayList[bucketCount];
        for (int i = 0; i < bucketCount; i++) {
            buckets[i] = new ArrayList<>();
        }
        
        // 分配元素到桶
        for (int num : arr) {
            int bucketIndex = (num - min) / range;
            buckets[bucketIndex].add(num);
        }
        
        // 桶内排序并合并
        int index = 0;
        for (List<Integer> bucket : buckets) {
            if (!bucket.isEmpty()) {
                if (bucket.size() <= 15) {
                    insertionSort(bucket);
                } else {
                    Collections.sort(bucket);
                }
                for (int num : bucket) {
                    arr[index++] = num;
                }
            }
        }
    }
    
    // 3. 优化版2：使用链表桶和自定义排序（减少扩容开销）
    public static void bucketSortLinkedList(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        
        int min = arr[0], max = arr[0];
        for (int num : arr) {
            if (num < min) min = num;
            if (num > max) max = num;
        }
        
        // 修复1：合理计算桶数量（参考其他优化版）
        int bucketCount = (int) Math.sqrt(arr.length) + 1;
        // 修复2：计算每个桶的范围，避免索引越界
        int range = (max - min) / bucketCount + 1;
        
        // 使用链表作为桶
        LinkedList<Integer>[] buckets = new LinkedList[bucketCount];
        for (int i = 0; i < bucketCount; i++) {
            buckets[i] = new LinkedList<>();
        }
        
        // 分配元素（修复3：使用range计算索引）
        for (int num : arr) {
            int bucketIndex = (num - min) / range;
            buckets[bucketIndex].add(num);
        }
        
        // 合并结果
        int index = 0;
        for (LinkedList<Integer> bucket : buckets) {
            if (!bucket.isEmpty()) {
                bucket.sort(null);
                for (int num : bucket) {
                    arr[index++] = num;
                }
            }
        }
    }
    
    // 4. 优化版3：并行桶排序（多线程处理）
    public static void bucketSortParallel(int[] arr) throws InterruptedException {
        if (arr == null || arr.length <= 1) {
            return;
        }
        
        int min = arr[0], max = arr[0];
        for (int num : arr) {
            if (num < min) min = num;
            if (num > max) max = num;
        }
        
        int bucketCount = Runtime.getRuntime().availableProcessors();
        int range = (max - min) / bucketCount + 1;
        
        List<Integer>[] buckets = new ArrayList[bucketCount];
        for (int i = 0; i < bucketCount; i++) {
            buckets[i] = new ArrayList<>();
        }
        
        // 分配元素
        for (int num : arr) {
            int bucketIndex = (num - min) / range;
            buckets[bucketIndex].add(num);
        }
        
        // 多线程并行排序
        Thread[] threads = new Thread[bucketCount];
        for (int i = 0; i < bucketCount; i++) {
            final int bucketIdx = i;
            threads[i] = new Thread(() -> {
                if (!buckets[bucketIdx].isEmpty()) {
                    Collections.sort(buckets[bucketIdx]);
                }
            });
            threads[i].start();
        }
        
        // 等待所有线程完成
        for (Thread thread : threads) {
            thread.join();
        }
        
        // 合并结果
        int index = 0;
        for (List<Integer> bucket : buckets) {
            for (int num : bucket) {
                arr[index++] = num;
            }
        }
    }
    
    // 辅助方法：对List进行插入排序
    private static void insertionSort(List<Integer> list) {
        for (int i = 1; i < list.size(); i++) {
            int key = list.get(i);
            int j = i - 1;
            while (j >= 0 && list.get(j) > key) {
                list.set(j + 1, list.get(j));
                j--;
            }
            list.set(j + 1, key);
        }
    }
    
    public static void main(String[] args) throws InterruptedException {
        double[] arr1 = {0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434};
        int[] arr2 = {43, 32, 22, 78, 63, 57, 91, 13, 25, 87};
        int[] arr3 = {43, 32, 22, 78, 63, 57, 91, 13, 25, 87};
        int[] arr4 = {43, 32, 22, 78, 63, 57, 91, 13, 25, 87};
        
        bucketSortBasic(arr1);
        System.out.println("基本版（浮点数）: " + Arrays.toString(arr1));
        
        bucketSortIntegers(arr2);
        System.out.println("整数优化版: " + Arrays.toString(arr2));
        
        bucketSortLinkedList(arr3);
        System.out.println("链表桶优化: " + Arrays.toString(arr3));
        
        bucketSortParallel(arr4);
        System.out.println("并行桶排序: " + Arrays.toString(arr4));
    }
}