对列表中的项目进行排序是一项很平常的任务，而且常常很耗时。术语排序通常是指根据预先指定的排序关系，以升序或降序排列列表中的项目。排序通常用于搜索，这是数据处理中的另一项基本活动。想象一下，如果字典里的单词没有被组织或分类，那么在字典里搜索单词是多么困难。这就是为什么字典里的词条是按标准的字母顺序排列的。通过排序，许多任务和计算变得毫不费力。这就是排序算法的用武之地。

排序算法只不过是一种将列表中的元素按特定顺序组织的方法，例如从最小值到最大值、从最大值到最小值、递增顺序、递减顺序、字母顺序等。最常用的顺序是数字顺序和字典顺序。算法通常使用排序作为关键子例程。有各种各样的排序算法贯穿始终，每一种都采用了一套丰富的技术。一种流行但同样强大的算法是分治算法，它是一种基于多分支递归的算法。快速排序和合并排序是基于分治算法的两种常用算法。

什么是快速排序(quick sort)？

快速排序是一种基于分而治之方法的高效排序算法，类似于将问题分解为两个子问题或多个子问题，然后递归求解的动态排序方法。如果子问题的大小足够小，那么它们就可以简单地以直接的方式解决，而不需要任何麻烦。快速排序算法也称为分区交换排序，它将要排序的列表分为三个主要部分：1）枢轴元素（中心元素），2）小于枢轴的元素，3）大于枢轴的元素。枢轴本身在两个组之间移动到最终位置，然后递归地应用快速排序。

什么是合并排序(merge sort)？

合并排序是另一种基于分治技术的通用排序算法。它是最受尊敬和流行的排序算法之一，设计用于高效地对外部存储在文件中的数据进行排序。在使用O（n）额外存储的最坏情况下，它提供O（n logn）行为。它将集合“a”划分为两个较小的集合，然后对每个集合进行排序。在最后阶段，这两个已排序的集合将合并回大小为n的单个集合。这将是排序列表。该算法是相当快，也是一个稳定的排序，是理想的首选链表。

快速排序和合并排序的区别

基础知识

–快速排序和合并排序都是基于分而治之的排序算法，其基本原理相同–将一个问题分成两个或多个子问题，然后递归求解。然而，它们在合并程序和性能方面有所不同。对于小数据集，快速排序通常比其他排序算法（包括合并排序）更好更快，而合并排序保持一致性，而不管数据集的类型如何。快速排序是理想的首选数组，而合并排序是理想的首选链表。

空间复杂性

–快速排序算法中的排序是递归进行的，每个递归调用都需要堆栈位置。它不需要额外的空间来进行合并，只需要一个内存空间来进行合并。由于它是就地排序算法，因此不需要额外的空间来执行排序。实际上，它在分割和合并数组时使用相同的数组。另一方面，在Merge-Sort中，有几种方法可以将数据表示为文件或数组，因此它需要像子文件或相同大小的数组这样的工作区，这些工作区需要额外的空间。

最坏情况复杂性

–快速排序的最坏情况发生在分区不平衡时，这取决于用于分区的元素，在这种情况下，算法与**排序一样缓慢地渐进运行。快速排序的最坏情况是O（n2），并留作练习。但是，可以通过选择正确的轴来避免这种情况。另一方面，合并排序的最坏情况发生在它必须进行最大数量的比较时。考虑到合并的线性性能，合并排序的最坏情况是O（nlog2n）。

演出

–尽管快速排序和合并排序算法都是基于分而治之的排序方法，但它们在执行拆分和合并过程的方法上有所不同。对于快速排序，大部分工作是将列表划分为两个子列表，这在子列表排序之前发生。对于合并排序，大部分工作是在对子列表进行排序之后合并两个子列表。合并排序需要一个临时数组来合并两个子数组，而快速排序不需要额外的数组空间，因此比Marge排序更节省空间。

快速排序与合并排序：比较图

总结 - 快速排序(of quick sort) vs. 合并排序(merge sort)

快速排序和合并排序算法都是基于分而治之的排序方法。但是，它们在执行拆分和合并过程时使用的方法不同。它们的工作原理基本相同——将一个问题分成两个或多个子问题，然后递归求解。在最坏的情况下，合并排序比快速排序更有效，但在平均情况下，两者的效率相同。但是快速排序比合并排序更节省空间。因此，快速排序无疑比合并排序更快更好，但在一些情况下（例如在比较时），它会变得效率低下。