使用快速排序算法来对归并排序的一部分进行排序？

Question

问题：Mergesort将数字列表分成两半，并在两个列表上递归调用自身。是否可以在左半部分执行快速排序，在右半部分执行归并排序？如果可以，请展示如何通过展示每个步骤来对以下数字列表进行排序。如果不行，请解释为什么不行。

我需要使用归并排序对数字列表进行排序，其中左半部分需要使用快速排序进行排序。

我想到了解决方法。

答案：是的，我们可以。

1.使用归并排序对数组的右半部分进行排序。 2.使用快速排序对左半部分进行排序。 3.使用merge_sort的合并函数将两个部分合并。

- purudpd

---

假设您打算在完成后合并“左半部分”和“右半部分”，那么使用哪种排序算法对于每个都无关紧要（您是否尝试使用原地快速排序以节省空间？）。并且，快速排序和归并排序都可以仅使用基本指针和序列长度作为参数在C中轻松实现。创造性的指针算术将通过最小的努力消除一个索引（低索引）。完全有可能我误解了您提出的问题，如果是这样，请澄清您实际上想要做什么？ - WhozCraig

我更新了问题。同时，从您的回复中，我发现可以在排序后合并这两半部分。谢谢您。 - purudpd

Answer 1

可以的，合并排序的基本思路如下：

1. 将数组分成两个或更多的部分。
2. 独立地对每个部分进行排序。
3. 应用合并步骤将排好序的部分组合成一个整体有序列表。

从正确性的角度来看，在第2部分生成的列表中，实际上并不重要您如何对其进行排序。所有需要做的就是对这些列表进行排序。合并排序的典型实现通过递归地将自己应用于左半部分和右半部分来完成第2部分，但您并没有必须这么做的根本原因。（事实上，在一些优化版本的合并排序中，当数组变得足够小时，您特别会切换到像插入排序这样的算法而不是递归应用合并排序）。

在你的情况下，使用快速排序（quicksort）在左侧和归并排序（mergesort）在右侧仍会产生一个排序序列。然而，它的工作方式看起来与你描述的方式相当不同。最终会发生这样的事情：数组的前一半会被快速排序（因为您快速排序了左半部分），然后您会递归地对右半部分进行排序。那一半会被快速排序，然后您会递归地对右半部分进行排序。那一半会被快速排序，以此类推。总体上，这将看起来像这样：

• 您将快速排序数组的前一半，然后是剩余部分的前一半，再然后是剩余部分的前一半等等，直到没有元素为止。
• 然后，从左到右工作，您将把最后两个元素合并在一起，然后是最后四个，然后是最后八个等等。

这将是一种非常酷的排序方式，但手动执行会非常痛苦。您最好编写一个程序来完成这个任务，并显示所有中间步骤。 :-)

- templatetypedef

Answer 2

不，你不能这样做。至少如果你还想称之为“归并排序”的话。归并排序和快速排序最根本的区别在于前者是一种稳定的算法，即相等的元素在排序后保持它们的相对位置不变。这在许多场景中都非常重要。

如果你使用快速排序来排序后半部分，相等元素的相对位置可能会改变（很有可能）。结果集将不再保持稳定性，因此不能再被视为归并排序。

顺便说一下，关于在归并排序的最后一步使用插入排序的问题，前面的回答是正确的。大多数高效的归并排序实现在元素数量较小时会使用类似插入排序的算法。插入排序也是稳定的，这就是为什么可以在不破坏归并排序稳定性的情况下使用它。

- Alexandre M