Méthode RandomizedQuickSort pour les tableaux

Question

Y a-t-il une méthode RandomizedQuickSort dans l'API java? OU nous devrions écrire son code nous-mêmes? merci

Answer 1

À moins que vous sachiez que Arrays.sort() ne fonctionnera pas pour vous, je vous suggère de l'utiliser. Sinon, je vous suggère de tester toute alternative est aussi bon qu'il le suggère.

J'ai ajouté ce qui suit à la source suggérée par @ org.life.java ainsi que des méthodes shuffle()/sort() qui devraient être à la fois randomisées et quicksorted.

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."); 
} 

et 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.