java - 为什么我的快速排序性能比合并排序差？

Question

我错过了什么吗？源代码很短，可以运行并进行评论以便更好地理解。我需要知道我做错了什么。

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;
    }

在主函数中，我运行了 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()));
        }
    }
}

Answer 1

这是我作为回答的评论:您对同一个列表进行了两次排序，因此第二次排序总是对一个已经排序的列表进行排序(这几乎总是与第一次排序的列表不同)。

试试你的主要代码的这个变体:

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);
        List<Integer> arreglo2 = new ArrayList<>(arreglo); // Make a copy

        startTime = System.nanoTime();
        QuickSort(arreglo);                                // Sort the original
        endTime = System.nanoTime();

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

        startTime = System.nanoTime();
        MergeSort(arreglo2);                               // Sort the copy
        endTime = System.nanoTime();

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