数组的 RandomizedQuickSort 方法

Question

java API中有RandomizedQuickSort方法吗？或者我们应该自己编写它的代码？ 谢谢

Answer 1

除非您知道 Arrays.sort() 不会为您工作，否则我建议您使用它。否则，我建议您测试任何替代方案是否如其建议的那样好。

我将以下内容添加到 @org.life.java 建议的源代码中，以及 shuffle()/sort() 方法，这些方法应该是随机和快速排序的。

long runTimeNS = 2 * 1000 * 1000 * 1000L;
for (int i = 0; i < 3; i++) {
    long start = System.nanoTime();
    long r;
    for (r = 1; r < runTimeNS; r++) {
        Arrays.sort(list7.clone());
        if (System.nanoTime() - start > runTimeNS) break;
    }
    long time = System.nanoTime() - start;
    System.out.println("Average Arrays.sort() time " + time / r / 1000 + " us.");

    long start1 = System.nanoTime();
    for (r = 1; r < runTimeNS; r++) {
        List<Integer> list = new ArrayList<Integer>();
        for (int j : list7) list.add(j);
        Collections.shuffle(list);
        Collections.sort(list);
        int[] ints = new int[list.size()];
        for (int j = 0; j < list.size(); j++) ints[j] = list.get(j);
        if (System.nanoTime() - start1 > runTimeNS) break;
    }

    long time1 = System.nanoTime() - start1;
    System.out.println("Average shuffle/sort time " + time1 / r / 1000 + " us.");

    long start2 = System.nanoTime();
    for (r = 1; r < runTimeNS; r++) {
        qrsort(list7.clone());
        if (System.nanoTime() - start2 > runTimeNS) break;
    }

    long time2 = System.nanoTime() - start2;
    System.out.println("Average qrsort() time " + time2 / r / 1000 + " us.");
}

它打印

Average Arrays.sort() time 477 us.
Average shuffle/sort time 5964 us.
Average qrsort() time 36155 us.
Average Arrays.sort() time 474 us.
Average shuffle/sort time 5894 us.
Average qrsort() time 35078 us.
Average Arrays.sort() time 480 us.
Average shuffle/sort time 6211 us.
Average qrsort() time 34790 us.