基于Java实现计数排序、桶排序和基数排序

计数排序（Counting Sort）

计数排序是一种稳定的排序算法，它使用一个计数数组来记录每个元素出现的次数，并按照次数将元素依次输出到结果数组中。

步骤

1. 初始化一个大小为 max_value 的空计数数组
2. 遍历待排序数组，将每个元素出现的次数加入计数数组对应下标中
3. 遍历计数数组，累加每个元素之前出现的次数，得到每个元素应该在排序后的数组中的位置
4. 将原数组元素按照计数数组排序并输出

代码示例

public static void countingSort(int[] arr, int max_value) {
    int[] count = new int[max_value + 1];

    for (int i = 0; i < arr.length; i++) {
        count[arr[i]]++;
    }

    for (int i = 1; i < count.length; i++) {
        count[i] += count[i - 1];
    }

    int[] output = new int[arr.length];
    for (int i = arr.length - 1; i >= 0; i--) {
        output[count[arr[i]] - 1] = arr[i];
        count[arr[i]]--;
    }

    for (int i = 0; i < arr.length; i++) {
        arr[i] = output[i];
    }
}

桶排序（Bucket Sort）

桶排序是一种分治思想的排序算法，它将待排序数据按照一定的规则（例如区间大小、位数等）分进若干个桶中，再分别对每个桶内元素排序，最后按照桶的顺序将所有元素依次取出即可。

步骤

1. 根据待排序元素的属性，确定分配到每个桶中元素的范围
2. 遍历待排序数组，将每个元素分别放入对应的桶中
3. 分别对每个桶内的元素进行排序
4. 将所有桶内元素按照顺序依次放回原始数组

代码示例

public static void bucketSort(int[] arr, int num_buckets) {
    // Step 1: Create empty buckets
    List<List<Integer>> buckets = new ArrayList<>();
    for (int i = 0; i < num_buckets; i++) {
        buckets.add(new ArrayList<>());
    }

    // Step 2: Fill buckets with data
    int max_value = Integer.MIN_VALUE;
    for (int value : arr) {
        max_value = Math.max(max_value, value);
        int bucketIndex = (num_buckets * value) / (max_value + 1);
        buckets.get(bucketIndex).add(value);
    }

    // Step 3: Sort each bucket
    for (List<Integer> bucket : buckets) {
        Collections.sort(bucket);
    }

    // Step 4: Merge sorted buckets into output array
    int index = 0;
    for (List<Integer> bucket : buckets) {
        for (int value : bucket) {
            arr[index++] = value;
        }
    }
}

基数排序（Radix Sort）

基数排序是一种按位排序算法，它根据待排序元素的位数，从低位到高位分别对元素进行桶排序，直到最高位排序完成。基数排序可以适用于非负整数的排序。

步骤

1. 将待排序数组按照个位数值放入桶中
2. 将桶中元素按照顺序依次排列，形成新的数组
3. 将新数组按照十位数值放入桶中
4. 重复 Step 2 和 3，直到最高位排序完成

代码示例

public static void radixSort(int[] arr, int max_digits) {
    int divisor = 1;
    for (int i = 0; i < max_digits; i++) {
        List<List<Integer>> buckets = new ArrayList<>();
        for (int j = 0; j < 10; j++) {
            buckets.add(new ArrayList<>());
        }

        for (int value : arr) {
            int digit = (value / divisor) % 10;
            buckets.get(digit).add(value);
        }

        int index = 0;
        for (List<Integer> bucket : buckets) {
            for (int value : bucket) {
                arr[index++] = value;
            }
        }

        divisor *= 10;
    }
}

示例说明

以下是一个基于计数排序的示例，排序前数组：[4,3,3,4,5,1,2,3,2,1,5]，排序后数组：[1,1,2,2,3,3,3,4,4,5,5]

int[] arr = {4,3,3,4,5,1,2,3,2,1,5};
countingSort(arr, 5);
System.out.println(Arrays.toString(arr));

以下是一个基于桶排序的示例，排序前数组：[3,6,9,12,3,7,10,8,5,6]，排序后数组：[3,3,5,6,6,7,8,9,10,12]

int[] arr = {3,6,9,12,3,7,10,8,5,6};
bucketSort(arr, 4);
System.out.println(Arrays.toString(arr));

以上是 Java 实现计数排序、桶排序、基数排序的完整攻略，根据不同场景选择不同的算法，可以实现高效的排序。