Я пытаюсь реализовать несколько алгоритмов сортировки на Java, чтобы сравнить производительность. Из того, что я прочитал, я ожидал, что quickSort будет быстрее, чем mergeSort, но в моем коде это не так, поэтому я предполагаю, что с моим алгоритмом quickSort должна быть проблема:
public class quickSortExample{
public static void main(String[] args){
Random gen = new Random();
int n = 1000000;
int max = 1500000;
ArrayList<Integer> d = new ArrayList<Integer>();
for(int i = 0; i < n; i++){
d.add(gen.nextInt(max));
}
ArrayList<Integer> r;
long start, end;
start = System.currentTimeMillis();
r = quickSort(d);
end = System.currentTimeMillis();
System.out.println("QuickSort:");
System.out.println("Time: " + (end-start));
//System.out.println(display(d));
//System.out.println(display(r));
}
public static ArrayList<Integer> quickSort(ArrayList<Integer> data){
if(data.size() > 1){
int pivotIndex = getPivotIndex(data);
int pivot = data.get(pivotIndex);
data.remove(pivotIndex);
ArrayList<Integer> smallers = new ArrayList<Integer>();
ArrayList<Integer> largers = new ArrayList<Integer>();
for(int i = 0; i < data.size(); i++){
if(data.get(i) <= pivot){
smallers.add(data.get(i));
}else{
largers.add(data.get(i));
}
}
smallers = quickSort(smallers);
largers = quickSort(largers);
return concat(smallers, pivot, largers);
}else{
return data;
}
}
public static int getPivotIndex(ArrayList<Integer> d){
return (int)Math.floor(d.size()/2.0);
}
public static ArrayList<Integer> concat(ArrayList<Integer> s, int p, ArrayList<Integer> l){
ArrayList<Integer> arr = new ArrayList<Integer>(s);
arr.add(p);
arr.addAll(l);
return arr;
}
public static String display(ArrayList<Integer> data){
String s = "[";
for(int i=0; i < data.size(); i++){
s += data.get(i) + ", ";
}
return (s+"]");
}
}
Результаты (для 1 миллиона целых чисел от 0 до 1500000):
mergeSort (также реализовано с arrayList): 1,3 секунды (в среднем) (0,7 секунды с int [] вместо этого)
quickSort: 3 секунды (в среднем)
Это просто плохой выбор моей опорной точки, или в алгоритме тоже есть недоработки.
Кроме того, есть ли более быстрый способ закодировать его с помощью int [] вместо ArrayList ()? (Как вы объявляете размер массива для массивов большего / меньшего размера?)
PS: Теперь можно реализовать его на месте, чтобы он использовал меньше памяти, но не в этом суть.
РЕДАКТИРОВАТЬ 1: я заработал 1 секунду, изменив метод concat. Спасибо!
