相关疑难解决方法(0)

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

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

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

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

关于so​​rt()的集合与数组有关sort()方法的这两个有什么区别？我知道Arrays的sort()正在使用二进制搜索sort(),那么Collections呢？以及如何选择使用哪个？谢谢!

我试图证明Clojure的性能可以与Java平等.我发现的一个重要用例是Quicksort.我写了一个如下实现:

(set! *unchecked-math* true)

(defn qsort [^longs a]
  (let [qs (fn qs [^long low, ^long high]
             (when (< low high)
               (let [pivot (aget a low)
                     [i j]
                     (loop [i low, j high]
                       (let [i (loop [i i] (if (< (aget a i) pivot)
                                             (recur (inc i)) i))
                             j (loop [j j] (if (> (aget a j) pivot)
                                             (recur (dec j)) j))
                             [i j] (if (<= i j)
                                     (let [tmp (aget a i)]
                                       (aset a i (aget a j)) (aset a …

为什么？它更快还是更有效？

对于具有一个核心的系统,我们可以使用quicksort.我们应该在具有两个内核,四个内核或八个内核的系统上使用什么？

java如何在内部对数据类型进行排序？为什么？如果可以提到具体的算法,那将是很好的

有几种排序算法,如计算机科学教科书中经常讨论的插入排序,选择排序,冒泡排序等.给定一个整数或对象数组,是否有内置的Java 6语言API,让我选择应用特定的排序算法来排序数组,而不是重新重新发明这些轮子？如果没有内置到Java 6中,是否有开源库可以生成这个功能,它们是什么？

我正在制作一个带有滚动视图的2D游戏(想想Red Alert或Zelda),但我正在绘制图纸.

基本上,地图上绘制了两种类型的对象.有些人有固定的位置(如树木和建筑物),有些则有移动(玩家,敌人,飞行箭头).

要使事物以正确的方式出现在彼此前面,需要按特定顺序绘制(首先是远处的物体并朝向"相机"工作).

现在我每次游戏更新(每秒100次)时都会对所有对象(两种)的列表进行排序,这感觉就像浪费了大量的CPU时间.对象的顺序很少变化,当它们发生时,它们通常只在列表中向上或向下移动一个位置.

另一个问题是只需要考虑实际在屏幕上的对象.由于地图可能变得非常大,有1000个物体,我不想每秒100次对它们进行排序.

你怎么建议我解决这个问题？

最近我将我们的应用程序jdk从Java 6更新为Java 8,但仍将源语言级别保持为Java 6.更改后,我们的一个单元测试失败了.我注意到LinkedList的Collections.sort在Java 8和Java 6中的工作方式不同.即使我是JDk 1.8的Source Level java 8,我也会得到相同的不同行为.要重新创建问题:定义下面的枚举:

public enum Weight {
    A(1), B(0), C(0), D(0), E(2);

    public int getWeight() {
        return weight;
    }

    private int weight;

    Weight(int weight) {

        this.weight = weight;
    }

    @Override
    public String toString() {
       return  name() + '(' + weight + ')';
    }
}

和一个主类如下:

public class Main {

    public static void main(String[] args) {
      List<Weight> weightList = new LinkedList<Weight>();
      weightList.add(Weight.A);
      weightList.add(Weight.B);
      weightList.add(Weight.C);
      weightList.add(Weight.D);
      weightList.add(Weight.E);

        Collections.sort(weightList, new Comparator<Weight>() {
            @Override
            public int compare(Weight …

以下代码的目标是对300,000个int数进行排序.我发现ArrayList的sort()的持续时间小于Arrays的sort().在内部,他们使用相同的算法进行排序.ArrayList使用Arrays的sort()来对其元素数据进行排序.

public class EasySort {
    public static void main(String args[]) {
        // Read data from file, number split by ","
        FileReader fr = null;
        try {
            fr = new FileReader("testdata2.txt");
        } catch (FileNotFoundException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }
        BufferedReader  bufferedReader=new BufferedReader(fr);
        String line=null;
        try {
            line=bufferedReader.readLine();
        } catch (IOException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }

        // use split method to generate a String array to save numbers
        String[] strArray=line.split(",");

        //Convert string array to …

我为QuickSort创建了一些改进,并决定针对Java进行测试Arrays.sort().

结果令人着迷:

在Java 6上:

• 我的时间/系统时间= 74/83 = 0.891566265060241
• 我的时间/系统时间= 75/79 = 0.9493670886075949
• 我的时间/系统时间= 75/84 = 0.8928571428571429

在Java 7上:

• 我的时间/系统时间= 115/70 = 1.6428571428571428
• 我的时间/系统时间= 101/76 = 1.3289473684210527
• 我的时间/系统时间= 102/61 = 1.6721311475409837

正如您所看到的,我的算法在Java 6上的表现更好,但是我不明白它对Java 7的影响有多大.可能你能找到原因吗？

编辑:我的算法如何工作:

• 步骤1:取3个数字,对它们进行排序,使用中间数作为枢轴
• 步骤2:将所有大于枢轴的数字向右移动,将所有数字小于向左旋转的数字,并将枢轴放置在已排序数组中的最终位置.这实际上是在O(N)中实现的.
• 步骤3:递归地重复步骤1和2的左侧和右侧.当富集小于12个元素的子数组时,使用网络排序对其进行排序.

我的源代码

public class QuickSort {

    public static void sort(int[] source) {
        int buffer[] = new int[source.length];
        concatenate(source, buffer, 0, source.length);
    }

    private static void concatenate(int[] source, int[] buffer, int low, int high) {
        int count = high - …