快速排序与合并排序

快速排序 是一种基于分治策略的内部算法。在这方面：

• 元素数组被反复划分为多个部分，直到无法进一步划分为止。
• 它也被称为 “分区交换排序” .
• 它使用一个关键元素（pivot）对元素进行分区。
• 一个左分区包含所有小于枢轴的元素，一个右分区包含所有大于关键元素的元素。

合并排序 是一种基于分治策略的外部算法。在这方面：

• 元素被一次又一次地拆分为两个子数组（n/2），直到只剩下一个元素。
• 合并排序使用额外的存储对辅助数组进行排序。
• 合并排序使用三个数组，其中两个用于存储每一半，第三个外部数组用于通过合并其他两个来存储最终排序的列表，然后递归地对每个数组进行排序。
• 最后，合并所有子数组，使其成为数组的“n”元素大小。

快速排序与合并排序

1. 数组中元素的分区 : 在合并排序中，数组被分成两部分（即n/2）。 鉴于 在快速排序的情况下，数组被分成任意比例。没有强制要求以快速排序方式将元素数组分成相等的部分。
2. 最坏情况复杂性 : 快速排序的最坏情况复杂度为O（n2），因为在最坏情况下需要进行大量比较。 鉴于 在合并排序中，最坏情况和平均情况具有相同的复杂性O（n logn）。
3. 使用数据集 : 合并排序可以很好地处理任何类型的数据集，无论其大小（大或小）。 鉴于 快速排序不能很好地处理大型数据集。
4. 额外存储空间要求 : 合并排序不到位，因为它需要额外的内存空间来存储辅助数组。 鉴于 快速分拣已经就位，因为它不需要任何额外的存储。
5. 效率 : 在数组大小或数据集较大的情况下，合并排序比快速排序效率更高，工作速度更快。 鉴于 在数组大小或数据集较小的情况下，快速排序比合并排序效率更高，工作速度更快。
6. 排序方法 : 快速排序是在内存中对数据进行排序的内部排序方法。 鉴于 合并排序是一种外部排序方法，在这种方法中，要排序的数据不能容纳在内存中，并且需要辅助内存来进行排序。
7. 稳定性 : 合并排序是稳定的，因为两个值相等的元素在已排序的输出中以与在未排序的输入数组中相同的顺序出现。 鉴于 在这种情况下，快速排序是不稳定的。但是，通过对代码进行一些更改，它可以变得稳定。
8. 首选 : 对于阵列，首选快速排序。 鉴于 对于链表，首选合并排序。
9. 参考位置 : 快速排序具有良好的缓存局部性，这使得快速排序比合并排序更快（在许多情况下，如在虚拟内存环境中）。