java – 为什么我的quicksort性能比我的mergesort差？

package com.company;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.*;

public class Main {

    public static ArrayList<Integer> randomArrayList(int n)
    {
        ArrayList<Integer> list = new ArrayList<>();
        Random random = new Random();

        for (int i = 0; i < n; i++)
        {
            list.add(random.nextInt(n));
        }
        return list;
    }

    public static List<Integer> MergeSort(List<Integer> A) throws  Exception{

        if (A.size()==1)
            return A;

        int mid = A.size()/2;

        List<Integer> left = A.subList(0,mid);
        List<Integer> right = A.subList(mid,A.size());

        left = MergeSort(left);
        right = MergeSort(right);
        A = Merge(left,right);

        return A;
    }

    public static List<Integer> Merge(List<Integer> L,List<Integer> R) throws  Exception{

        List<Integer> output = new ArrayList<Integer>(Collections.nCopies(L.size() + R.size(),0));

        int i = 0; int j = 0; int k = 0;
        while (i < L.size() && j < R.size()) {
            if (L.get(i) < R.get(j)) {
                output.set(k,L.get(i));
                i=i+1;
            }
            else {
                output.set(k,R.get(j));
                j=j+1;
            }
            k++;
        }
        while (i < L.size()) {
            output.set(k,L.get(i));
            i=i+1;
            k++;
        }
        while (j < R.size()) {
            output.set(k,R.get(j));
            j=j+1;
            k++;
        }

        return output;
    }

    public static List<Integer> QuickSort(List<Integer> A) throws  Exception{

        if (A.size()==1 || A.size()==0)
            return A;

        //The pivot is a random element of the array A
        int randomIndex = new Random().nextInt(A.size());
        Integer P = A.get(randomIndex);

        //Swap first element of A with selected pivot
        Integer tmp;
        A.set(randomIndex,A.get(0));
        A.set(0,P);

        //Initiate i and l (partition analysis progress counters)
        int l = 0,i = l + 1,r = A.size();


        for (int j = l + 1; j < r; j++ ){
            if (A.get(j)< P ){
                //Swap A[j] and A[i]
                tmp = A.get(j);
                A.set(j,A.get(i));
                A.set(i,tmp);
                //Increase i by 1 (counting the pos of already partitioned)
                i = i + 1;
            }
        }

        //Swap A[l] (Pivot) and A[i-1] most left element bigger than pivot
        tmp = A.get(l);
        A.set(l,A.get(i-1));
        A.set(i - 1,tmp);

        QuickSort(A.subList(0,i-1));
        QuickSort(A.subList(i,A.size()));

        return A;
    }

在main函数中,我运行20次两种方法进行比较.您可以复制代码的两个部分并运行它

public static void main(String[] args) throws Exception{

        long startTime,endTime,duration;

        //Compare 20 times QuickSort vs MergeSort
        for (int i=0;i<20;i++){

            List<Integer> arreglo = randomArrayList(100000);

            startTime = System.nanoTime();
            QuickSort(arreglo);
            endTime = System.nanoTime();

            duration = (endTime - startTime)/1000000;
            System.out.println("Quicksort: " + Long.toString(duration));

            startTime = System.nanoTime();
            MergeSort(arreglo);
            endTime = System.nanoTime();

            duration = (endTime - startTime)/1000000;
            System.out.println("MergeSort: "+Long.toString(duration));

            //System.out.println(Arrays.toString(QuickSort(arreglo).toArray()));
            //System.out.println(Arrays.toString(MergeSort(arreglo).toArray()));
        }
    }
}