计数排序与基数排序

计数排序（Counting Sort）

适用范围：整数，且值域不大（如 0~k）。

public void countingSort(int[] arr) {
    if (arr.length == 0) return;
    int max = Arrays.stream(arr).max().getAsInt();
    int[] count = new int[max + 1];
    for (int x : arr) count[x]++;
    // 前缀和（稳定排序）
    for (int i = 1; i <= max; i++) count[i] += count[i-1];
    int[] out = new int[arr.length];
    for (int i = arr.length - 1; i >= 0; i--) {
        out[--count[arr[i]]] = arr[i];
    }
    System.arraycopy(out, 0, arr, 0, arr.length);
}

时间：O(n + k)，空间：O(n + k)。

桶排序（Bucket Sort）

将数据分桶，桶内各自排序后合并。

public void bucketSort(float[] arr) {
    int n = arr.length;
    List<Float>[] buckets = new ArrayList[n];
    for (int i = 0; i < n; i++) buckets[i] = new ArrayList<>();
    for (float x : arr) {
        int idx = (int) (x * n);   // x 在 [0,1)
        buckets[idx].add(x);
    }
    int p = 0;
    for (List<Float> b : buckets) {
        Collections.sort(b);
        for (float v : b) arr[p++] = v;
    }
}

基数排序（Radix Sort）

按位从低到高做计数排序（LSD，最低位优先）。

public void radixSort(int[] arr) {
    int max = Arrays.stream(arr).max().getAsInt();
    for (int exp = 1; max / exp > 0; exp *= 10) {
        countingSortByDigit(arr, exp);
    }
}

private void countingSortByDigit(int[] arr, int exp) {
    int[] count = new int[10];
    int[] out = new int[arr.length];
    for (int x : arr) count[(x / exp) % 10]++;
    for (int i = 1; i < 10; i++) count[i] += count[i-1];
    for (int i = arr.length - 1; i >= 0; i--) {
        int digit = (arr[i] / exp) % 10;
        out[--count[digit]] = arr[i];
    }
    System.arraycopy(out, 0, arr, 0, arr.length);
}

时间：O(d·(n+k))，d 是位数，k=10（十进制）。

应用题：最大间距（LeetCode 164）

排序后，相邻元素最大差值。要求线性时间。

桶排序思路：n 个元素放 n+1 个桶，最大间距必然跨桶，只需看相邻非空桶的最小最大值。

public int maximumGap(int[] nums) {
    if (nums.length < 2) return 0;
    int min = Arrays.stream(nums).min().getAsInt();
    int max = Arrays.stream(nums).max().getAsInt();
    if (min == max) return 0;
    int n = nums.length;
    int bucketSize = Math.max(1, (max - min) / (n - 1));
    int bucketCount = (max - min) / bucketSize + 1;
    int[] bMin = new int[bucketCount], bMax = new int[bucketCount];
    Arrays.fill(bMin, Integer.MAX_VALUE);
    Arrays.fill(bMax, Integer.MIN_VALUE);
    for (int x : nums) {
        int idx = (x - min) / bucketSize;
        bMin[idx] = Math.min(bMin[idx], x);
        bMax[idx] = Math.max(bMax[idx], x);
    }
    int gap = 0, prevMax = min;
    for (int i = 0; i < bucketCount; i++) {
        if (bMin[i] == Integer.MAX_VALUE) continue;
        gap = Math.max(gap, bMin[i] - prevMax);
        prevMax = bMax[i];
    }
    return gap;
}

应用题：前K个高频元素（LeetCode 347）

桶排序 O(n)：统计频次，以频次为桶下标。

public int[] topKFrequent(int[] nums, int k) {
    Map<Integer, Integer> freq = new HashMap<>();
    for (int x : nums) freq.merge(x, 1, Integer::sum);
    List<Integer>[] buckets = new ArrayList[nums.length + 1];
    for (var e : freq.entrySet()) {
        int f = e.getValue();
        if (buckets[f] == null) buckets[f] = new ArrayList<>();
        buckets[f].add(e.getKey());
    }
    List<Integer> res = new ArrayList<>();
    for (int i = buckets.length - 1; i >= 0 && res.size() < k; i--) {
        if (buckets[i] != null) res.addAll(buckets[i]);
    }
    return res.stream().mapToInt(x -> x).toArray();
}