读书笔记-《数据结构与算法》-摘要8[桶排序]

桶排序和归并排序有那么点点类似，也使用了归并的思想。大致步骤如下：

设置一个定量的数组当作空桶。
Divide - 从待排序数组中取出元素，将元素按照一定的规则塞进对应的桶子去。
对每个非空桶进行排序，通常可在塞元素入桶时进行插入排序。
Conquer - 从非空桶把元素再放回原来的数组中。

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

public class BucketSort {

    public static void main(String[] args) {
        int[] arr = {80, 50, 30, 10, 90, 60, 0, 70, 40, 20, 50};
        System.out.println("Original array: " + Arrays.toString(arr));

        bucketSort(arr);

        System.out.println("Sorted array: " + Arrays.toString(arr));
    }

    public static void bucketSort(int[] arr) {
        // 获取数组中的最大值和最小值
        int max = getMax(arr);
        int min = getMin(arr);

        // 计算桶的数量
        int bucketCount = (max - min) / arr.length + 1;

        // 创建桶列表
        List<List<Integer>> buckets = new ArrayList<>(bucketCount);
        for (int i = 0; i < bucketCount; i++) {
            buckets.add(new ArrayList<>());
        }

        // 将数组中的每个元素放入对应的桶中
        for (int num : arr) {
            int index = (num - min) / arr.length;
            buckets.get(index).add(num);
        }

        // 对每个桶中的元素进行排序，并将结果合并到原数组中
        int index = 0;
        for (List<Integer> bucket : buckets) {
            Collections.sort(bucket);
            for (int num : bucket) {
                arr[index++] = num;
            }
        }
    }

    private static int getMax(int[] arr) {
        int max = arr[0];
        for (int num : arr) {
            if (num > max) {
                max = num;
            }
        }
        return max;
    }

    private static int getMin(int[] arr) {
        int min = arr[0];
        for (int num : arr) {
            if (num < min) {
                min = num;
            }
        }
        return min;
    }
}