用于排序物料合并排序得快速排序？
问题：Mergesort将一个数字列表分成两半，并对这两个数字进行递归调用。相反，您能在左半部分执行quicksort，在右半部分执行mergesort吗？如果是，则通过显示每个步骤来显示它将如何对下面的数字列表进行排序。如果没有，请解释为什么不能。
Iam应该使用MergeSort对数字列表进行排序。左半部分将使用快速排序进行排序？
我想出来了。安：是的，我们可以
- 使用mergeSort对数组的右半部分进行排序。
- 使用快速排序对左半部分进行排序。
- 使用MERGE_SORT的merge函数合并2。
共有2个答案
不，你做不到。至少如果您仍然希望将其称为“合并排序”。合并排序和快速排序最根本的区别在于，第一种是一种稳定的算法，即等序元素在排序后保持其相对位置不变。这在许多情况下都很重要。如果使用快速排序对后半部分进行排序，则相等元素的相对位置可能（而且很可能会）改变。结果集将无法保持稳定性，因此不能仍然将其视为合并排序。
顺便说一下，前面的答案是正确的，关于插入排序用作合并排序的最后一步。大多数高效的合并排序实现将在元素数量较小时使用类似插入排序的方法。插入排序也是稳定的，这就是为什么它可以在不破坏合并排序稳定性的情况下进行。
是的，你能做到的。mergesort背后的基本思想如下：
- 将数组拆分为两个（或多个）部分。
- 对每一段进行独立排序。
- 应用合并步骤将已排序的内容组合为一个整体排序列表。
从正确性的角度来看，您如何对第（2）部分中生成的列表进行排序实际上并不重要。重要的是要对这些列表进行排序。mergesort的一个典型实现是通过递归地将自身应用到左右半部分来完成步骤（2）的，但没有必要这样做的根本原因。（事实上，在mergesort的一些优化版本中，您特别不这样做，而是在数组变得足够小时切换到像插入排序这样的算法）。
在您的例子中，在左侧使用quicksort，在右侧使用mergesort仍然会生成一个排序序列，这是正确的。然而，它的工作方式与您描述的完全不同。最终发生的事情是这样的：数组的前半部分将被快速排序（因为您快速排序了左半部分），然后您将递归排序右半部分。前半部分将快速排序，然后递归排序右半部分。前半部分将快速排序，等等。总体来看，这将是如下所示的：
- 快速排序数组的前半部分，然后是剩下的前半部分，然后是剩下的前半部分，等等，直到没有剩下的元素为止。
- 然后，从左到右，将最后两个元素合并在一起，然后是最后四个元素，最后八个元素，等等。
这将是一个相当酷的看起来，但做它的手将是一个完全的痛苦。您最好编写一个程序来完成这些操作，并显示所有的中间步骤。：-）
-
快速排序 from typing import List def quick_sort(arr: List, left, right) -> List: """ 快速排序是对冒泡排序的改进，核心思想是找到一个中值点pivot，然后将小于等于pivot的放在pivot的左边，大于pivot的放在右边，一直递归到无法拆分pivot点。 :param arr: :re
-
在处理接近排序的数组时，哪种算法的快速排序或合并排序性能更好？为什么？我意识到，在这种情况下，其他算法可能会比这些算法表现得更好。
-
问题内容： [http://jsperf.com/optimized-mergesort-versus- quicksort][1] 为什么这个半缓冲区合并排序的工作速度与quicksort一样快？ QuickSort是： 就地虽然会占用递归（堆栈空间） 缓存友好 这一半缓冲区合并排序： 使用Buffer进行合并。 使用递归。 进行较少的比较。 我的问题是，在这种情况下，为什么半缓冲区合并排序与Q
-
问题内容： 如何为Java实现并发的quicksort或mergesort算法？ 我们在16（虚拟）核的Mac上遇到问题，其中只有一个核（！）使用默认的Java排序算法工作，而且很好的机器没有得到充分利用是不好的。因此，我们编写了自己的代码（我编写了代码），并且确实取得了不错的提速（我编写了多线程快速排序，由于其分区特性，它可以很好地并行化，但我也可以编写合并排序）……但是我的实现只能扩展最多4个
-
本文向大家介绍JavaScript希尔排序、快速排序、归并排序算法，包括了JavaScript希尔排序、快速排序、归并排序算法的使用技巧和注意事项，需要的朋友参考一下 以var a = [4,2,6,3,1,9,5,7,8,0];为例子。 1.希尔排序。 希尔排序是在插入排序上面做的升级。是先跟距离较远的进行比较的一些方法。 过程输出： 由输出可以看到。第一轮间隔为5。依次对这些间隔的数组插入排序
-
快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要 Ο(nlogn) 次比较。在最坏状况下则需要 Ο(n2) 次比较，但这种状况并不常见。事实上，快速排序通常明显比其他 Ο(nlogn) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。 快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两