sorting - QuickSort 用于排序部分 Mergesort？

Question

问题:Mergesort 将一个数字列表分成两半，并在这两部分上递归调用自己。相反，您可以在左半部分执行快速排序并在右半部分执行合并排序吗？如果是，请显示它将如何通过显示每个步骤对以下数字列表进行排序。如果不是，请解释为什么不能。

我应该使用合并排序对数字列表进行排序。使用快速排序对左半部分进行排序的位置？

我想到了。
答:是的，我们可以

使用归并排序对数组的右半部分进行排序。

使用快速排序对左半部分进行排序。

使用merge_sort 的合并函数合并2。

Answer 1

是的，你可以这样做。归并排序的基本思想如下:

将数组拆分为两个(或更多)部分。

独立地对每一块进行排序。

应用合并步骤将排序后的部分合并为一个整体排序列表。

从正确性的角度来看，如何对第 (2) 部分中生成的列表进行排序实际上并不重要。重要的是这些列表得到排序。合并排序的典型实现通过将自身递归地应用于左右半部分来完成步骤 (2)，但没有根本原因您必须这样做。 (实际上，在某些优化版本的归并排序中，您特别不这样做，而是在数组足够小时时切换到插入排序之类的算法)。

在您的情况下，您是正确的，在左侧使用快速排序并在右侧使用合并排序仍然会产生排序序列。但是，它的工作方式看起来与您所描述的完全不同。最终会发生的事情是这样的:数组的前半部分会被快速排序(因为你对左半部分进行了快速排序)，然后你会递归地对右半部分进行排序。前半部分会被快速排序，然后你会递归地对右半部分进行排序。前半部分会得到快速排序，等等。总的来说，这看起来像这样:

你快速排序数组的前半部分，然后是剩下的前半部分，然后是剩下的前半部分，等等，直到没有元素剩下。

然后，从左到右，您将最后两个元素合并在一起，然后是最后四个元素，然后是最后八个元素，依此类推。

这将是一种看起来很酷的类型，但手动完成将是一个痛苦的过程。您最好编写一个仅执行此操作并显示所有中间步骤的程序。 :-)