当前位置:  开发笔记 > 编程语言 > 正文

Quicksort比Mergesort慢?

如何解决《Quicksort比Mergesort慢?》经验,为你挑选了1个好方法。

我昨天正在努力实现一个快速排序,然后我运行它,期望比Mergesort更快的运行时间(我也已实现).我运行了两个,虽然快速排序对于较小的数据集<100个元素更快(并且我确实验证了它的工作原理),但mergesort很快就成为了更快的算法.有人告诉我,quicksort几乎总是比mergesort"更快",我理解这个话题有一些争论,但我至少预计它会比这更接近.对于数据集> 10000个元素,mergesort的速度提高了4倍以上.这是预期的,还是我的快速排序代码中有错误?

归并排序:

public static void mergeSort(int[ ] e)
{
    if (e.length <= 1) return;
    int[] first = new int[e.length/2];
    int[] second = new int[e.length - first.length];
    System.arraycopy(e, 0, first, 0, first.length);
    System.arraycopy(e, first.length, second, 0, second.length);
    mergeSort(first);
    mergeSort(second);
    System.arraycopy(merge(first, second), 0, e, 0, e.length);
}

private static int[] merge(int[] first, int[] second) {
    int iFirst = 0;
    int iSecond = 0;
    int iCombined = 0;

    int[] combined = new int[first.length + second.length];
    while(iFirst < first.length && iSecond < second.length) {
        if (first[iFirst] > second[iSecond]) {
            combined[iCombined++] = second[iSecond++];
        }
        else combined[iCombined++] = first[iFirst++];
    }
    for(; iFirst < first.length; iFirst++) {
        combined[iCombined++] = first[iFirst];
    }
    for(; iSecond < second.length; iSecond++) {
        combined[iCombined++] = second[iSecond];
    }
    return combined;
}

快速排序:

public static void quicksort(int[] a, int first, int last) {
    if (first >= last) return;

    int partitionIndex = partition(a, first, last);
    quicksort(a, first, partitionIndex - 1);
    quicksort(a, partitionIndex + 1, last);
}

public static int partition(int[] x, int first, int last) {
    int left = first;
    int right = last;
    int pivot = x[first];
    int pivotIdx = first;

    while(left <= right) {
        while(left < x.length && x[left] <= pivot) left++;
        while(right >= 0 && x[right] > pivot) right--;
        if (left <= right) {
            int temp = x[left];
            x[left] = x[right];
            x[right] = temp;
        }
    }
    pivotIdx = right;
    x[first] = x[right];
    x[pivotIdx] = pivot;
    return pivotIdx;
}

小智.. 10

我实际上只是在C中编写了一个"链表比较排序演示程序"并得出了类似的结论(mergesort将在大多数情况下击败quicksort),尽管我被告知快速排序通常不会用于链接列表.我会注意到,枢轴值的选择是一个怪物因素 - 我的初始版本使用随机节点作为枢轴,当我稍微改进它以取两个(随机)节点的平均值时,1000000记录的exectution时间从超过4分钟到不到10秒,使其与mergesort相提并论.

Mergesort和quicksort具有相同的大O最佳情况(n*log(n)),尽管人们可能试图声称,但是大O实际上是关于迭代计数而不是比较计数.两者之间可以产生的最大区别总是对快速排序有害,并且它涉及已经大量排序或包含大量关系的列表(当快速排序比mergesort更好时,差异几乎不会如此大).这是因为关系或已经排序的段直接通过mergesort流线化; 当两个拆分列表返回合并时,如果一个列表已经包含所有较小的值,则左侧的所有值将一次一个地比较到右边的第一个元素,然后(因为返回的列表具有内部秩序)没有进一步需要进行比较,并将权利简单地迭代到最后.也就是说,迭代次数将保持不变,但比较次数减少一半.如果你在谈论实际时间并且正在排序字符串,那就是昂贵的比较.

如果未仔细确定枢轴值,则快速排序中的联系和已排序的分段很容易导致不平衡的列表,并且不平衡的列表(例如,右侧的一个,左侧的十个)是导致减速的原因.因此,如果你可以让你的快速排序在已经排序的列表上执行,就像在ramdomized列表上一样,你有一个很好的方法来找到支点.

如果您有兴趣,演示程序会生成如下输出:

[root~/C] ./a.out -1 3 
Using "", 0 records
Primary Criteria offset=128

Command (h for help, Q to quit): N
How many records? 4000000
New list is 562500.00 kb

Command (h for help, Q to quit): m

Mergesorting..............3999999 function calls
123539969 Iterations     Comparison calls: 82696100
Elapsed time: 0 min 9 sec


Command (h for help, Q to quit): S
Shuffled.

Command (h for help, Q to quit): q

Quicksorting..............4000000 function calls
190179315 Iterations     Comparison calls: 100817020
Elapsed time: 0 min 23 sec

Altho没有krazy kolors.关于它,我在这个页面的一半左右有更多的东西.

PS.两种类型都不需要链表的额外内存.



1> 小智..:

我实际上只是在C中编写了一个"链表比较排序演示程序"并得出了类似的结论(mergesort将在大多数情况下击败quicksort),尽管我被告知快速排序通常不会用于链接列表.我会注意到,枢轴值的选择是一个怪物因素 - 我的初始版本使用随机节点作为枢轴,当我稍微改进它以取两个(随机)节点的平均值时,1000000记录的exectution时间从超过4分钟到不到10秒,使其与mergesort相提并论.

Mergesort和quicksort具有相同的大O最佳情况(n*log(n)),尽管人们可能试图声称,但是大O实际上是关于迭代计数而不是比较计数.两者之间可以产生的最大区别总是对快速排序有害,并且它涉及已经大量排序或包含大量关系的列表(当快速排序比mergesort更好时,差异几乎不会如此大).这是因为关系或已经排序的段直接通过mergesort流线化; 当两个拆分列表返回合并时,如果一个列表已经包含所有较小的值,则左侧的所有值将一次一个地比较到右边的第一个元素,然后(因为返回的列表具有内部秩序)没有进一步需要进行比较,并将权利简单地迭代到最后.也就是说,迭代次数将保持不变,但比较次数减少一半.如果你在谈论实际时间并且正在排序字符串,那就是昂贵的比较.

如果未仔细确定枢轴值,则快速排序中的联系和已排序的分段很容易导致不平衡的列表,并且不平衡的列表(例如,右侧的一个,左侧的十个)是导致减速的原因.因此,如果你可以让你的快速排序在已经排序的列表上执行,就像在ramdomized列表上一样,你有一个很好的方法来找到支点.

如果您有兴趣,演示程序会生成如下输出:

[root~/C] ./a.out -1 3 
Using "", 0 records
Primary Criteria offset=128

Command (h for help, Q to quit): N
How many records? 4000000
New list is 562500.00 kb

Command (h for help, Q to quit): m

Mergesorting..............3999999 function calls
123539969 Iterations     Comparison calls: 82696100
Elapsed time: 0 min 9 sec


Command (h for help, Q to quit): S
Shuffled.

Command (h for help, Q to quit): q

Quicksorting..............4000000 function calls
190179315 Iterations     Comparison calls: 100817020
Elapsed time: 0 min 23 sec

Altho没有krazy kolors.关于它,我在这个页面的一半左右有更多的东西.

PS.两种类型都不需要链表的额外内存.

推荐阅读
360691894_8a5c48
这个屌丝很懒,什么也没留下!
DevBox开发工具箱 | 专业的在线开发工具网站    京公网安备 11010802040832号  |  京ICP备19059560号-6
Copyright © 1998 - 2020 DevBox.CN. All Rights Reserved devBox.cn 开发工具箱 版权所有