如何通用化计数排序实现按x/y/z任意字段排序Point对象数组

业内常规的实现方式是采用**键提取器（Key Extractor）**模式，逻辑和你熟悉的比较器lambda一致，专门用来抽象“从对象中提取指定排序键”的逻辑，不需要修改原有类，也不需要额外前置处理。

Java 8+ 最简实现 #

直接用JDK自带的ToIntFunction<T>函数式接口作为参数，通用排序方法代码如下：

import java.util.function.ToIntFunction;

private static Point[] countSort(Point[] arr, int max, ToIntFunction<Point> keyExtractor) {
    int[] cnt = new int[max + 1];
    for (Point ele : arr) {
        int sortKey = keyExtractor.applyAsInt(ele);
        cnt[sortKey]++;
    }
    for (int i = 1; i < cnt.length; i++) {
        cnt[i] += cnt[i - 1];
    }
    
    Point[] ret = new Point[arr.length];
    for (int i = arr.length - 1; i >= 0; i--) {
        Point ele = arr[i];
        int sortKey = keyExtractor.applyAsInt(ele);
        ret[cnt[sortKey] - 1] = ele;
        cnt[sortKey]--;
    }
    return ret;
}

调用示例 #

和比较器的lambda用法完全一致：

// 按x坐标排序，maxX为x坐标的最大取值
Point[] sortedByX = countSort(originArr, maxX, p -> p.x);
// 按y坐标排序，maxY为y坐标的最大取值
Point[] sortedByY = countSort(originArr, maxY, p -> p.y);
// 按z坐标排序，maxZ为z坐标的最大取值
Point[] sortedByZ = countSort(originArr, maxZ, p -> p.z);

低版本Java兼容实现 #

如果用的是Java 8之前的版本，无法使用内置函数式接口，自己定义一个简单的键提取器接口即可：

// 自定义键提取接口
public interface PointKeyExtractor {
    int getSortKey(Point p);
}

// 调整排序方法的参数类型
private static Point[] countSort(Point[] arr, int max, PointKeyExtractor extractor) {
    // 内部逻辑和上面完全一致，调用extractor.getSortKey(ele)获取键值即可
}

// 调用示例（匿名内部类写法）
Point[] sortedByX = countSort(originArr, maxX, new PointKeyExtractor() {
    @Override
    public int getSortKey(Point p) {
        return p.x;
    }
});

方案优势 #

• 无侵入性：不需要修改Point类的原有代码
• 扩展性强：后续如果Point新增其他int类型的排序字段，不需要调整排序方法，直接传入对应键提取逻辑即可
• 无额外开销：不需要在方法外提前生成排序键数组，仅在遍历过程中实时提取键值，性能和单独写的三个排序方法完全一致
• 保留特性：原有计数排序的稳定性完全不受影响

你提到的两种方案的不足 #

1. 外部提前生成sortBy数组：会产生额外的O(n)空间占用，调用逻辑冗余，没有必要
2. Point新增char参数的get方法：扩展性差，后续新增字段需要修改Point类的get方法，违反开闭原则，硬编码的字符标识也容易引发传参错误

内容的提问来源于stack exchange，提问作者Will Kanga