Ordenar método aleatorio rápido para las matrices

Question

¿Hay RandomizedQuickSort método en la API de Java? O debemos escribir su código nosotros mismos? gracias

Answer 1

A menos que sepa que Arrays.sort () no va a trabajar para usted, le sugiero que utilice. De lo contrario, le sugiero que pruebe cualquier alternativa es tan buena como lo sugiere.

He añadido los métodos que se deben tanto al azar y con quicksorted siguiente a la fuente sugerido por @ org.life.java así como una reproducción aleatoria () / 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.");
}

e imprime

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.