相关疑难解决方法(0)

Java 6的Arrays.sort方法使用Quicksort作为基元数组,并对对象数组进行合并排序.我相信大多数时候Quicksort比合并排序更快,并且内存更少.我的实验支持这一点,尽管两种算法都是O(n log(n)).那么为什么不同的算法用于不同的类型呢？

我们知道快速排序是最快的排序算法.

collections.sort使用合并排序算法而不是快速排序.但是Arrays.sort使用快速排序.

Collections.sort使用合并排序而不是快速排序的原因是什么？

我试着做一个测试,关于Collection.sort()和Arrays.sort().在测试中,我创建了一个int长度为1e5100 的s 数组,其中包含从1到1e5的随机数.我还创建了一个类型列表Integer,它在与数组相同的位置包含相同的值.然后我使用Arrays.sort()和列表使用排序数组Collections.sort().

更新:正如@Holger指出的那样,我的代码有一个错误.修正后的代码现在是:

import java.util.* ;


class TestClass {
    public static void main(String args[] ) throws Exception {
        double ratSum = 0 ;
        for(int j=0;j<100;j++)
        {
        int[] A = new int[(int)1e5] ;
        List<Integer> L = new ArrayList<Integer>() ;
        for(int i=0;i<A.length;i++)
        {
            int no = (int)(Math.random()*(int)1e5) ;
            A[i] = no ;
            L.add(A[i]) ;
        }

        long startTime = System.nanoTime() ;
        Arrays.sort(A) ;
        long endTime = System.nanoTime() …

给定的通用数据类型看起来像这样:HashMap<EdgeTuple, Double> edgeList其中元组是一个类EdgeTuple而Double是一个对任务不重要的权重:

class EdgeTuple{
    int label1;
    int label2;
    public EdgeTuple(int label1, int label2){
        int min = Math.min(label1, label2);
        int max = Math.max(label1, label2);
        this.label1 = min;
        this.label2 = max;
    }
}

因此,您可以看到元组已经在第一个位置上具有较小的值.我想要做的是对最终输入顺序应该如下所示的列表进行排序:

条目0:[(0,某事物); some_weight]

第1项:[(1,某事); some_weight]

...

条目n-1:[(last_value,something); some_weight]

所以基本上我需要做的是对元组的第一个值进行升序排序.我对这个主题的红色最喜欢的现有答案,但仍然找不到令人满意的东西.

一种可能的解决方案是依靠比较器,如下所示:

Comparator<Tuple> myComparator = new Comparator<Tuple>() {
    public int compare(Tuple t1, Tuple t2) {
        //the comparison rules go here
    }
};
Collections.sort(tupleList, myComparator);

每对元组的比较似乎并不安静.所以我的问题是,您是否知道其他任何排序方式？也许一些新的数据类型为给定的任务提供了一个合适的更高性能的接口？

谢谢