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

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

在main函数中我运行20次比较两种方法。可以复制两段代码和运行 it

    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

使用 int[] 数组而不是 ArrayList 包装器 class 可能会提高一些性能。通用列表 classes 存在开销，可能无法优化。
将 (left + right) / 2 替换为您的随机主元代码也将消除一些开销，从而提高性能。
QuickSort 特定，在较小的子数组上使用 InsertionSort 比分区更有效。
最后，避免递归调用将降低堆栈使用率，从而提高性能。

这是一些 Java 脚本（抱歉，我没有 Java 版本，如果你愿意，可以翻译它）。执行应该很快。

/*
QUICK SORT IN PLACE
Use iterative approach with stack
Use insertion sort for small subsets
*/
function quickSortIP(arr) {
    var stack = [];
    var left = 0;
    var right = arr.length - 1;
    var i, j, swap, temp;
    while(true) {
        if(right - left <= 25){
            for(j=left+1; j<=right; j++) {
                swap = arr[j];
                i = j-1;
                while(i >= left && arr[i] > swap) {
                    arr[i+1] = arr[i--];
                }
                arr[i+1] = swap;
            }
            if(stack.length === 0)    break;
            right = stack.pop();
            left = stack.pop();
        } else {
            var median = (left + right) >> 1;
            i = left + 1;
            j = right;
            swap = arr[median]; arr[median] = arr[i]; arr[i] = swap;
            if(arr[left] > arr[right]) {
                swap = arr[left]; arr[left] = arr[right]; arr[right] = swap;
            } if(arr[i] > arr[right]) {
                swap = arr[i]; arr[i] = arr[right]; arr[right] = swap;
            } if(arr[left] > arr[i]) {
                swap = arr[left]; arr[left] = arr[i]; arr[i] = swap;
            }
            temp = arr[i];
            while(true){
                do i++; while(arr[i] < temp);
                do j--; while(arr[j] > temp);
                if(j < i)    break;
                swap = arr[i]; arr[i] = arr[j]; arr[j] = swap;
            }
            arr[left + 1] = arr[j];
            arr[j] = temp;
            if(right - i + 1 >= j - left){
                stack.push(i);
                stack.push(right);
                right = j - 1;
            }else{
                stack.push(left);
                stack.push(j - 1);
                left = i;
            }
        }
    }
    return arr;
}

Answer 2

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

试试你的主代码的这个变体：

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

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

Why is my quicksort performance worse than my mergesort?

java

algorithm

quicksort

analysis

mergesort