在java中对对象数组进行排序的最快方法

Question

我有一个名为apple的类,包含3个值int x,int y和int weight.然后我创建了一个苹果类型对象的数组.现在我想根据权重对对象数组进行排序,这意味着具有最低权重的苹果对象应该是第一个,依此类推.

我知道有很多方法可以通过使用Arrays.sort等或比较器来实现这一点.

我想知道在Java中这种方法的最快方法是什么？可能有一个案例,我有500,000个对象,所以我想知道我应该使用哪种,更重要的是哪种方法会给我最好的方法.我甚至用Hoare分区编写了自己的快速排序.

Apple类的代码

public class Apple {
    public int x;
    public int y;
    public int weight;

    public Apple(int a, int b, int w) {
        x = a;
        y = b;
        weight = w;
    }
}

主类代码

public class main {
    static Apple[] appleArray;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int size = sc.nextInt();
        int totalApples = sc.nextInt();
        appleArray = new Edge[totalApples];
        int x = 10;
        int y = 20;
        int w = 30;

        for (int i = 0; i < size; i++) {
            appleArray[i] = new Apple(x, y, w);
            x++;
            y++;
            w++;
        }
        //Now i want to sort array of apple objects based on weight
    }
}

Answer 1

本书有一个有用的备忘单,可以根据您的需求确定最佳排序:https://www.safaribooksonline.com/library/view/algorithms-in-a/9780596516246/ch04s09.html

最简单的解决方案

该Arrays.sort命令使用快速排序实现,适用于许多情况.对于您的示例代码,这可能是:

Arrays.sort(appleArray, new Comparator<Apple>(){  
    @Override  
    public int compare(Apple apple1, Apple apple2){  
         return apple1.weight - apple2.weight;  
    }  
}); 

最快的解决方案

在您的情况下,您有一个包含重复的大型数组,例如阵列中的50,000个苹果可能都重3盎司...因此,您可能选择实施存储桶排序以提高快速排序的性能,这在这种情况下可能会浪费.这是一个示例实现.

也许基准一些研究选择,在适合的时候使用Java API来确定输入集的最佳解决方案.

Answer 2

我首先使用Java API.如果这还不够快,那么我会搜索优化的排序库.

还考虑一个数据库,数据库引擎快速并优化用于排序大型数据集.