桶排序和计数排序java

桶排序和计数排序是两种不同的排序算法。

桶排序的基本思想是将数组分到有限数量的桶里，再对每个桶中的元素进行排序，最后按照桶的顺序将元素依次列出来，形成有序序列。桶排序的时间复杂度取决于对每个非空桶进行排序时所选择的排序算法。当要排序的数据均匀分布时，桶排序可以达到线性时间复杂度。

计数排序是一种记录数据出现次数的排序算法。它的原理类似于桶排序，可以看作是一种特殊的桶排序算法。计数排序遍历序列，并将每个元素放入对应的桶中。然后按照桶的顺序将元素依次放回原来的序列中。计数排序是一种稳定的排序算法，适用于数据范围较小的情况。

对于Java语言，你可以使用以下代码实现桶排序和计数排序：

桶排序的Java实现代码示例：

public void bucketSort(int[] arr, int bucketSize) {
    if (arr.length == 0) {
        return;
    }
    
    // 寻找数组的最大值和最小值
    int min = arr[0], max = arr[0];
    for (int i = 1; i < arr.length; i++) {
        if (arr[i] < min) {
            min = arr[i];
        } else if (arr[i] > max) {
            max = arr[i];
        }
    }
    
    // 桶的数量
    int bucketCount = (max - min) / bucketSize + 1;
    List<List<Integer>> buckets = new ArrayList<>();
    for (int i = 0; i < bucketCount; i++) {
        buckets.add(new ArrayList<>());
    }
    
    // 将数组中的元素放入对应的桶中
    for (int i = 0; i < arr.length; i++) {
        int bucketIndex = (arr[i] - min) / bucketSize;
        buckets.get(bucketIndex).add(arr[i]);
    }
    
    // 对每个桶中的元素进行排序，并放回原来的序列中
    int index = 0;
    for (int i = 0; i < bucketCount; i++) {
        List<Integer> bucket = buckets.get(i);
        Collections.sort(bucket);
        for (int j = 0; j < bucket.size(); j++) {
            arr[index++] = bucket.get(j);
        }
    }
}

计数排序的Java实现代码示例：

public void countingSort(int[] arr) {
    if (arr.length == 0) {
        return;
    }
    
    // 寻找数组的最大值和最小值
    int min = arr[0], max = arr[0];
    for (int i = 1; i < arr.length; i++) {
        if (arr[i] < min) {
            min = arr[i];
        } else if (arr[i] > max) {
            max = arr[i];
        }
    }
    
    // 计算数组中每个元素的出现次数
    int[] counts = new int[max - min + 1];
    for (int i = 0; i < arr.length; i++) {
        counts[arr[i] - min]++;
    }
    
    // 将计数数组中的元素依次放回原来的序列中
    int index = 0;
    for (int i = 0; i < counts.length; i++) {
        while (counts[i] > 0) {
            arr[index++] = i + min;
            counts[i]--;
        }
    }
}