如何用计数排序对Enum排序？Java是否有标准实现机制？

Great question! Let's break this down clearly: Java's standard library does not include a built-in utility specifically for counting-sorting objects by Enum keys, but because Enums represent a fixed, finite set of constants, implementing an efficient O(n) counting sort (or bucket sort variant) is straightforward and far more performant than using Arrays.sort for large datasets.

First: A Quick Note on Your Existing Implementation #

Your current EnumComparator uses toString() to compare Enum keys, which works but isn't the most efficient or type-safe approach. Since Enums have a natural order (via ordinal(), based on their declaration order) or can have custom ordering (like your MyEnum's index field), you could optimize the comparator to use these directly instead of string comparisons. But even with that optimization, Arrays.sort still runs in O(n log n) time.

Implementing O(n) Counting Sort for Enum-Keyed Beans #

The core idea is to leverage the fixed size of your Enum: create a "bucket" (list) for each Enum constant, place each Bean into the bucket matching its key, then concatenate the buckets in your desired order. This runs in O(n) time because we only traverse the input array once, plus a fixed number of operations to iterate over the Enum constants.

Here's a tailored implementation for your code:

Step 1: Refactor the Bean Class (Optional but Recommended) #

First, make the key field a specific Enum type instead of the generic Enum—this adds type safety and avoids casting later:

class Bean {
    public Object data;
    public MyEnum key; // Use specific Enum type
    public Bean(Object data, MyEnum key) {
        this.data = data;
        this.key = key;
    }
    @Override
    public String toString() {
        return key.toString();
    }
}

Step 2: Full Working Implementation #

We'll create a method that sorts the Bean array using bucket sorting, optimized for Enum keys:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Main {
    // Predefine the desired sort order of your Enum constants
    private static final MyEnum[] DESIRED_ENUM_ORDER = {MyEnum.A, MyEnum.B, MyEnum.C, MyEnum.D};
    // Precompute a map for O(1) lookup of Enum to bucket index
    private static final Map<MyEnum, Integer> ENUM_TO_INDEX = new HashMap<>();
    
    static {
        for (int i = 0; i < DESIRED_ENUM_ORDER.length; i++) {
            ENUM_TO_INDEX.put(DESIRED_ENUM_ORDER[i], i);
        }
    }

    public static void main(String[] args) throws Exception {
        Bean[] mass = new Bean[] {
            new Bean(new Object(), MyEnum.A),
            new Bean(new Object(), MyEnum.C),
            new Bean(new Object(), MyEnum.D),
            new Bean(new Object(), MyEnum.B),
            new Bean(new Object(), MyEnum.A)
        }; 

        sortBeansByEnumKey(mass);
        System.out.println(Arrays.toString(mass)); // Output: [1, 1, 2, 3, 4]
    }

    public static void sortBeansByEnumKey(Bean[] beans) {
        // Initialize buckets for each Enum constant
        List<Bean>[] buckets = new List[DESIRED_ENUM_ORDER.length];
        for (int i = 0; i < buckets.length; i++) {
            buckets[i] = new ArrayList<>();
        }

        // Place each Bean into its corresponding bucket
        for (Bean bean : beans) {
            int bucketIndex = ENUM_TO_INDEX.get(bean.key);
            buckets[bucketIndex].add(bean);
        }

        // Concatenate buckets back into the original array
        int currentPosition = 0;
        for (List<Bean> bucket : buckets) {
            for (Bean bean : bucket) {
                beans[currentPosition++] = bean;
            }
        }
    }
}

class Bean {
    public Object data;
    public MyEnum key;
    public Bean(Object data, MyEnum key) {
        this.data = data;
        this.key = key;
    }
    @Override
    public String toString() {
        return key.toString();
    }
}

enum MyEnum {
    D("4"), A("1"), B("2"), C("3");
    private String index;
    private MyEnum(String index) {
        this.index = index;
    }
    @Override
    public String toString() {
        return index;
    }
}

Why This Is O(n) #

• Traversing the input array to fill buckets takes O(n) time.
• Concatenating the buckets also takes O(n) time (since every Bean is moved exactly once).
• The Enum constant count is fixed (let's call it k), so operations like initializing buckets or iterating over the Enum order are O(k)—a constant that doesn't grow with the input size.
• Total time complexity: O(n + k) = O(n) (since k is fixed).

If You Want to Use the Enum's Natural Declaration Order #

If you don't need a custom order and just want to sort by the Enum's natural declaration order, replace DESIRED_ENUM_ORDER with MyEnum.values():

private static final MyEnum[] DESIRED_ENUM_ORDER = MyEnum.values();

Just note that ordinal() (which values() uses) is based on the order the Enum constants are declared—so in your MyEnum, this would order them as D, A, B, C unless you reorder the declaration.

Key Takeaways #

• Java doesn't have a built-in Enum-specific counting sort, but rolling your own is simple and efficient.
• This approach beats Arrays.sort's O(n log n) time, especially for large arrays.
• Using a precomputed map for Enum-to-index lookups ensures the sort stays O(n) without hidden overhead.

内容的提问来源于stack exchange，提问作者Denis Vabishchevich