用于排序零件Mergesort的QuickSort？
Ques：Mergesort将数字列表分成两半，并对它们进行递归调用。 相反，你可以在左半边执行快速排序，在右半部分执行快速排序？ 如果是，请展示如何通过显示每一步来对以下数字列表进行排序。 如果不是，请解释为什么你不能。
Iam应该使用mergesort对数字列表进行排序。 使用快速排序对左半部分进行排序？
我想到了。 Ans：是的，我们可以
是的，你可以做到这一点。 mergesort背后的基本思想如下：
从正确性的角度来看，实际上并不关心你如何对第（2）部分生成的列表进行排序。 重要的是这些列表得到排序。 mergesort的一个典型实现通过递归地将它自己应用于左右两半来执行步骤（2），但是没有必要这么做的根本原因。 （事实上，在一些优化版本的mergesort中，你特别不要这样做，而是在数组变得足够小时切换到插入排序等算法）。
在你的情况，你是正确的，左侧使用quicksort和右侧mergesort仍然会产生排序序列。 然而，它的工作方式与你所描述的看起来有很大的不同。 最终会发生的事情是这样的：数组的前半部分会被快速分类（因为你快速排列左半部分），然后你会递归地排序右半部分。 前半部分会被快速分类，然后你会递归排序右半部分。 前半部分会被快速分类，等等。总的来说，这看起来像这样：
这将是一个非常酷的类型，但手动完成将是一个完全痛苦。 你可能最好写一个只是做这个并显示所有中间步骤的程序。 :-)
不，你做不到。 至少如果你仍然想称之为“合并排序”。 合并排序和快速排序之间最根本的区别在于第一个是稳定的算法，即排序后排序相同的元素保持相对位置不变。 这在很多情况下很重要。 如果您使用快速排序对后半部分进行排序，则相等元素的相对位置可能（并且很可能会改变）。 结果集不会保持稳定性，因此它不能被视为合并排序。
顺便说一下，以前的答案对于用作合并排序的最后一步的插入排序是正确的。 当元素数量很少时，最有效的合并排序实现将使用类似插入排序的操作。 插入排序也是稳定的，这就是为什么它可以在不破坏合并排序稳定性的情况下完成。
链接地址: http://www.djcxy.com/p/31585.html