Quicksort比Mergesort慢？
我昨天正在努力实现一个快速排序，然后我运行它，期望比Mergesort更快的运行时间（我也已实现）。 我运行了两个，虽然快速排序对于较小的数据集<100个元素更快（并且我确实validation了它的工作原理），但mergesort很快就成为了更快的算法。 有人告诉我，快速排序几乎总是比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[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] = 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; }
我实际上只是在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。 两种类型都不需要链表的额外内存。
对于基于随机数组的数据，Mergesort要慢得多，只要它适合于ram。 这是我第一次看到它的争论。
- 先排序最短的子arrays。
- 切换到5-25元素以下的插入排序
- 进行正常的枢轴选择
你的qsort非常慢，因为它试图分区和qsort长度为2和3的数组。
之前在SO上讨论过：“ 为什么quicksort比mergesort更好？ ”
〜
快速排序对于相对较小的arrays大小的优点之一仅仅是硬件实现的人为因素。
在数组上，快速排序可以就地完成，这意味着您正在读取和写入相同的内存区域。 另一方面，Mergesort通常需要分配新缓冲区，这意味着您的内存访问更加分散。 您可以在示例实现中看到这两种行为。
因此，对于相对较小的数据集，快速排序更有可能获得缓存命中，因此在大多数硬件上运行速度更快。
正如您的实验所证实的那样，Mergesort对于大型数据集或其他数据结构（如链表）仍然是一个非常好的解决方案。
根据这个维基百科文章，您的结果是预期的。
合并排序最糟糕的情况是quicksort的平均情况，所以如果你没有一个好的实现，合并排序总体上会更快。 快速进入快速工作是为了避免亚平均情况。 选择一个更好的支点（中位数为3的帮助），你会看到差异。
我可以想象通过直接访问内存，例如使用C，可以比Mergesort提高Quicksort的性能。
另一个原因是Mergesort需要更多内存，因为很难将其作为就地排序实现。
特别是对于您的实现，您可以改进枢轴的选择，有很多不同的算法可以找到一个好的支点。
从维基百科可以看出，可以用不同的方式实现Quicksort。
（1）有一个qsort算法，由C qsort（）使用，不需要额外的内存。 这很可能是由Hoare发明的。 这使得qsort（）在C中快速。
（2）在运行qsort之前随机化数据几乎总能加快速度。
（3）选择枢轴的中值数据可以使其更快，
这与算法的分析一致。 对于任何输入和每个运行时，Merge-sort都保证为O（nlogn）。 Quicksort是最佳情况O（nlogn）和平均情况O（nlogn），但是最坏情况O（n ^ 2），因此平均执行将在O（nlogn）和O（n ^ 2）之间。
Quicksort是最好的一般情况算法，因为它具有较低的开销，因此它具有n的值高达约10000左右的良好速度，并且对于n的任意天文值仍然具有良好的运行时间。 Merge-sort具有写入堆栈帧的不幸开销，这是每次递归调用所必需的。 因此，对于低的n值，它在RT = cnlogn中具有非常高的c并且它不是优选的一般分类方法。
编辑：软件猴子指出了一个矛盾：Quicksort平均为O（nlogn）随机输入，但O（n ^ 2）最坏情况。 所以它实际上受到数据熵的限制 – 或者您可以随机选择枢轴。 我可能仍然有点偏僻。
如果在快速排序最坏情况下实现堆排序作为基本排序算法，则可以实现theta（n log n）算法。
如果你不需要稳定的排序，并且不对链表进行排序，我认为这是你能走的最快。
合并排序
我认为只要数据适合内存，良好的合并排序实现比良好的快速排序实现更好。
qsort（），glibc qsort（）最广泛使用的实现之一，在数据适合内存时，大多数情况下内部使用合并排序。 此合并排序分配用于合并的临时内存空间，这会增加一些内存开销，但大多数情况下，它通过良好的数据透视选择和优化优于其自己的内部快速排序实现。 当数据和用于合并排序的临时内存不能适合内存时，glibc仅使用quicksort。
我已经测量了我的机器上的这两个实现的性能，2.1GHz CPU和几GB RAM。 输入是用伪随机生成器生成的，每个键是32位无符号整数，这意味着由于比较函数的接口，比整数比较多一些比较周期。
对于合并排序：
2 MB, time_diff 165.156000 ms, 78.752518 ns per byte 4 MB, time_diff 344.298000 ms, 82.087040 ns per byte 8 MB, time_diff 730.926000 ms, 87.133169 ns per byte 16 MB, time_diff 1541.215000 ms, 91.863573 ns per byte 32 MB, time_diff 3088.924000 ms, 92.057109 ns per byte 64 MB, time_diff 6262.868000 ms, 93.324006 ns per byte 128 MB, time_diff 12887.018000 ms, 96.015766 ns per byte 256 MB, time_diff 26731.597000 ms, 99.582959 ns per byte
快速排序：
2 MB, time_diff 243.519000 ms, 116.118908 ns per byte 4 MB, time_diff 504.975000 ms, 120.395422 ns per byte 8 MB, time_diff 1075.276000 ms, 128.182888 ns per byte 16 MB, time_diff 2183.865000 ms, 130.168498 ns per byte 32 MB, time_diff 4343.993000 ms, 129.461080 ns per byte 64 MB, time_diff 8714.166000 ms, 129.851192 ns per byte 128 MB, time_diff 17881.344000 ms, 133.226395 ns per byte 256 MB, time_diff 36751.029000 ms, 136.908252 ns per byte
您可以看到这两个实现之间在性能上存在明显差异，以及为什么在这种广泛使用的qsort实现中，mergesort比quicksort更受欢迎。 这种差异背后的主要原因似乎是因为快速排序比合并排序有10-20％的比较，因为每一步的分割不均匀。
我运行了类似的测试，纯粹的快速排序（随机选择枢轴）比大型数组的合并排序慢得多。
选择枢轴作为第一个，中间和最后一个元素的中位数可以提高快速排序的性能，但快速排序仍然比大型arrays上的合并排序（> 100000个元素）更糟糕。
当我实现了intro-sort时，我看到了一个很大的改进，即如果递归深度超过某个阈值，快速排序会回落到堆排序。 我的intro-sort实现几乎与我的合并排序实现一样快。 当然，intro-sort不再是纯粹的快速排序，因为当纯粹的快速排序遇到一些不良数据时，它使用堆排序将复杂性带回n log（n）。 如果您有兴趣，我可以发布结果。
数据集是否足够随机？ 它们是否部分排序？
这可能会影响排序的速度……
就像QuickSort的分区（）一样，如果数字按顺序排列，你会跳过，直到找到一个不是。
它可能取决于您为测试排序的数据类型（已排序的列表，随机，反向排序）。 另外，如果你选择一个随机的数据透视而不是使用第一个元素，quicksort的速度可能会更快。
为了获得快速排序的良好性能，重要的是不要一直递减到长度为1的列表
如果需要，您应该考虑将2,3，甚至4的列表排序为嵌套ifs交换。 让我们知道性能如何变化。