Метод RandomizedQuickSort для массивов

Question

Есть ли способ RandomizedQuickSort в java API? ИЛИ мы должны сами написать свой код? спасибо

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.