我昨天正在努力实现一个快速排序,然后我运行它,期望比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.两种类型都不需要链表的额外内存.
我实际上只是在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.两种类型都不需要链表的额外内存.