递归快速排序比迭代快速排序更快>>

Question

我一直在比较递归Quicksort和迭代QuickSort的性能，似乎我的递归QuickSort始终比迭代版本快。我只是想知道是否有任何理由为什么递归版本会更快？根据我的理解，迭代版本应该执行得更快，因为它避免了递归调用的开销。

递归QuickSort实现

int Pivot = 1;
QuickSort cleanRun = new QuickSort(runArray, Pivot);
int last = runArray.length - 1;
long start = System.nanoTime();
cleanRun.quickSort(0, last);
long end = System.nanoTime();
递归快速排序类

public class QuickSort extends SortingAlgorithm {

    public QuickSort(int[] l, int pivot) {
        super(l);
    }


    public int[] getL() {
        return l;
    }

    public void quickSort(int first, int last) {
        int splitPoint;
        if (first < last) {
            splitPoint = split(first, last);
            quickSort(first, splitPoint - 1);
            quickSort(splitPoint + 1, last);
        }
    }

    private int split(int first, int last) {
        int splitPoint, unknown;
        int x;
        int temp;
        int temp2;

        x = l[first];

        splitPoint = first;
        for (unknown = first + 1; unknown <= last; unknown++) {
            if (l[unknown] < x) {
                splitPoint = splitPoint + 1;
                //interchange(splitPoint, unknown);
                temp = l[splitPoint];
                l[splitPoint] = l[unknown];
                l[unknown] = temp;
            }
        }
        temp = l[first];
        l[first] = l[splitPoint];
        l[splitPoint] = temp;
        return splitPoint;
    }
}
迭代式快速排序实现

    QuickSortStack cleanRun = new QuickSortStack(runArray);
    int last = runArray.length - 1;
    long start = System.nanoTime();
    cleanRun.explicitStackingQuicksortCustomPivot(runArray);
    long end = System.nanoTime();
迭代式快速排序类

public class QuickSortStack extends SortingAlgorithm {

    public QuickSortStack(int[] l) {
        super(l);
    }

    public int[] getL() {
        return l;
    }

    /**
     *
     * @param l
     */
    public void explicitStackingQuicksortCustomPivot(int l[]){
        //these are the indexes
        int first, last, splitPoint;
        Stack stack = new Stack();
        stack.push(0);
        last = l.length-1;
        stack.push(last);
        while(!stack.empty())
        {
            last = (int) stack.pop();
            first = (int) stack.pop();
            while(first < last){
                splitPoint = split2(first, last);
                stack.push (splitPoint+1);
                stack.push(last);
                last = splitPoint - 1;
            }
        }
    }

    /**
     *
     * @param first
     * @param last
     * @return
     */
    private int split2(int first, int last) {
        int splitPoint, unknown;
        int x;
        int temp;
        x = l[first];
        splitPoint = first;
        for (unknown = first + 1; unknown <= last; unknown++) {
            if (l[unknown] < x) {
                splitPoint = splitPoint + 1;
                //interchange(splitPoint, unknown);
                temp = l[splitPoint];
                l[splitPoint] = l[unknown];
                l[unknown] = temp;
            }
        }
        temp = l[first];
        l[first] = l[splitPoint];
        l[splitPoint] = temp;
        return splitPoint;
    }
}

我一直在比较递归Quicksort和迭代QuickSort的性能，似乎我的递归QuickSort始终比迭代版本快。我只是想知道是否...

Answer 1

这里是使用数组作为堆栈的迭代快速排序。它比具有类似逻辑的递归版本快约10％。 （对于递归版本，递归发生在较小的分区上，然后循环回较大的分区以将递归深度限制为log2（n）。）