java - QuickSort 与 MergeSort，我做错了什么？

Question

我正在尝试用 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+"]");
}

}

结果(在 0 到 1500000 之间的 100 万个整数上):

mergeSort(也用 arrayList 实现):1.3 秒(平均)(用 int[] 代替 0.7 秒)

快速排序:3 秒(平均)

是我的支点选择不好，还是算法也有一些缺陷。

还有，有没有比 ArrayList() 更快捷的编码方式？ (如何为更大/更小的数组声明数组的大小？)

PS:我现在可以以一种就地方式实现它，因此它使用更少的内存，但这不是本文的重点。

编辑 1:我通过更改 concat 方法获得了 1 秒。 谢谢!

Answer 1

PS: I now it is possible to implement it in an inplace manner so it uses less memory, but this is not the point of this.

这不仅仅是为了使用更少的内存。您在“concat”例程中所做的所有额外工作而不是进行适当的就地快速排序几乎肯定是成本如此之高的原因。如果您无论如何都可以使用额外的空间，那么您应该始终编写合并排序代码，因为与快速排序相比，它往往会进行更少的比较。

想一想:在“concat()”中，您不可避免地必须再次遍历子列表，进行更多比较。如果您就地进行了交换，全部在一个数组中，那么一旦您决定交换两个位置，就不会再做出决定。