快速排序和归并排序有什么区别？
我是否正确地说，在这两种算法中，您所做的只是获取结构，递归地将其分成两部分，然后以正确的顺序构建结构？
那么，有什么区别呢？
编辑：我找到了以下用于在快速排序中实现分区的算法，但我不太明白它是如何工作的，特别是使用 (hi + low) >>> 的 swop 行1 作为参数！有人能理解这一点吗？
private static int partition( int[] items, int lo, int hi )
{
int destination = lo;
swop( items, (hi + lo) >>> 1, hi );
// The pivot is now stored in items[ hi ].
for (int index = lo; index != hi; index ++)
{
if (items[ hi ] >= items[ index ])
{
// Move current item to start.
swop( items, destination, index );
destination ++;
}
// items[ i ] <= items[ hi ] if lo <= i < destination.
// items[ i ] > items[ hi ] if destination <= i <= index.
}
// items[ i ] <= items[ hi ] if lo <= i < destination.
// items[ i ] > items[ hi ] if destination <= i < hi.
swop( items, destination, hi );
// items[ i ] <= items[ destination ] if lo <= i <= destination.
// items[ i ] > items[ destination ] if destination < i <= hi.
return destination;
}
Am I right in saying that in both algorithms, all you're doing is taking your structure, recursively splitting it into two, and then building up your structure in the right order?
So, what is the difference?
Edit : I have found the following algorithm for implementing the partition in quicksort, but I don't really understand how it works, , specifically the swop line that uses (hi + low) >>> 1 as an argument! Can anyone make sense of this?
private static int partition( int[] items, int lo, int hi )
{
int destination = lo;
swop( items, (hi + lo) >>> 1, hi );
// The pivot is now stored in items[ hi ].
for (int index = lo; index != hi; index ++)
{
if (items[ hi ] >= items[ index ])
{
// Move current item to start.
swop( items, destination, index );
destination ++;
}
// items[ i ] <= items[ hi ] if lo <= i < destination.
// items[ i ] > items[ hi ] if destination <= i <= index.
}
// items[ i ] <= items[ hi ] if lo <= i < destination.
// items[ i ] > items[ hi ] if destination <= i < hi.
swop( items, destination, hi );
// items[ i ] <= items[ destination ] if lo <= i <= destination.
// items[ i ] > items[ destination ] if destination < i <= hi.
return destination;
}
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（6）
是的。然而，不同之处在于结构何时以正确的顺序构建。在快速排序中，实际的排序步骤是在拆分期间完成的（将元素移动到左半部分或右半部分，具体取决于与枢轴元素的比较），并且没有合并步骤来恢复树（从数据点观察到）当然，你的实现可能有堆栈展开），而在合并排序中，排序是在向上的过程中完成的——拆分步骤根本不移动元素，但在返回的过程中，你需要合并两个已排序的列表。
至于性能比较：确实，快速排序的最坏情况行为比合并排序更糟糕，但平均情况的常数因子（几乎完全在实践中观察到）较小，这使得快速排序通常是通用、未排序输入的获胜者。并不是很多人需要自己实现通用排序例程......
Yes. The difference, however, is in when the structure is built in the right order. In Quicksort, the actual sorting step is done during the splitting (move elements to the left or right half, depending on the comparison with the pivot element) and there is no merging step to get back up the tree (as observed from the data point of view; your implementation may of course have stack unwinding), while in Mergesort, the sorting is done on the way up – the splitting step does not move elements at all, but on the way back up, you need to merge two sorted lists.
As for the performance comparisons: It is certainly true that the worst-case behavior of Quicksort is worse than that of Mergsesort, but the constant factor for the average case (which is observed almost exclusively in practice) is smaller, which makes Quicksort usually the winner for generic, unsorted input. Not that many people need to implement generic sorting routines themselves …
在最坏的情况下，快速排序的复杂度为 O(n^2)，而归并排序的复杂度为 O(n*log n)
快速排序使用主元，并以主元为参考点对两个部分进行排序，但存在主元为最大或最小的风险的排序数组。如果您选择错误的主元，您最终会得到复杂性 n^2（n^2 比较）
所谓的合并排序基于递归地将数组分成相同大小的两半并将它们合并回来。例如，wikipedia 上的解释非常好。尤其是树状制动的图片似乎很好地解释了这一点。
In worst case quicksort will have O(n^2) where mergesort will be O(n*log n)
Quicksort uses a pivot and sorts the two parts with the pivot as reference point with the risk that the pivot will be either maximum or minimum of the sorted array. If you will be choosing the wrong pivots you will end up with complexity n^2 (n^2 comparsions)
Mergesort as named is based on recursively dividing array into halfs of the same size and merging them back. Pretty nice explanations on wikipedia for example. Especially the picture with the tree-like brakedown seems to explain it pretty well.
快速排序有一个糟糕的最坏情况，而合并排序总是保证 O(n log n)，但典型的快速排序实现在实践中比合并排序更快。
此外，合并排序需要额外的存储，这在许多情况下都是一个问题（例如库例程）。这就是为什么库例程几乎总是使用快速排序。
这是取 hi 和 low 的平均值，相当于 (hi + low) / 2。
Quicksort has a bad worst case, while Mergesort is always O(n log n) guaranteed, but typical Quicksort implementations are faster than Mergesort in practice.
Also, Mergesort requires additional storage, which is a problem in many cases (e.g. library routines). This is why Quicksort is almost always used by library routines.
This is taking the average of hi and low, equivalent to (hi + low) / 2.
底层数据结构的实现细节也是一个因素，例如高效的随机访问（快速排序所需），并且数据结构的可变性也会影响内存需求（特别是合并排序）
The implementation details of the underlying data-structures would also be a factor such as efficient random access (needed by quicksort) and the mutability of data-structures would have an effect on the memory requirements (particularly mergesort)
是的，快速排序和归并排序都是分治算法。
Wikipedia 的 Quicksort 页面 有一个简短的比较：
Yes, both Quicksort and Mergesort are divide-and-conquer algorithms.
Wikipedia's Quicksort page has a brief comparison:
http://en.wikipedia.org/wiki/Sorting_algorithm 在这里您可以快速了解常见的排序算法。快速排序和合并排序是前两种；）
有关更多信息，请阅读有关每种算法的信息。
正如 Jan 所说，归并排序的复杂度始终为 O(n * log n)，而快速排序在最坏情况下可达 O(n^2)
http://en.wikipedia.org/wiki/Sorting_algorithm there you have a quick overview of common sort algorithms. Quicksort and Mergesort are the first two ;)
For more information read through the information given on each of these algorithms.
As Jan said, Mergesort has always a complexity of O(n * log n) and Quicksort is up to O(n^2) in worstcase