为什么数组首选快速排序，链表首选合并排序？

为什么 快速排序 首选阵列？

下面是数组的快速排序和合并排序的递归和迭代实现。

数组的递归快速排序。 数组的迭代快速排序。 数组的递归合并排序 数组的迭代合并排序

• 一般形式的快速排序是就地排序（即不需要任何额外存储），而合并排序需要O（N）额外存储，N表示可能非常昂贵的数组大小。分配和取消分配用于合并排序的额外空间会增加算法的运行时间。
• 比较平均复杂度，我们发现这两种类型的排序都有O（NlogN）平均复杂度，但常数不同。对于阵列，由于使用了额外的O（N）存储空间，合并排序会丢失。
• 快速排序的大多数实际实现都使用随机版本。随机版本的时间复杂度预计为O（nLogn）。最坏的情况在随机化版本中也是可能的，但最坏的情况不会出现在特定的模式（如排序数组）中，随机化快速排序在实践中效果很好。
• 快速排序也是一种缓存友好的排序算法，因为它具有良好的性能 参考位置 用于阵列时。
• 快速排序也很重要 尾部递归 因此，尾部调用优化已经完成。

为什么 合并排序 首选链接列表？

下面是单链表和双链表的快速排序和合并排序的实现。

双链表的快速排序 单链表的快速排序 单链表的合并排序 双链表的合并排序

• 万一 链表 这种情况之所以不同，主要是因为数组和链表的内存分配不同。与数组不同，链表节点在内存中可能不相邻。
• 与数组不同，在 链表 我们可以在O（1）额外空间和O（1）时间中插入项目，如果我们给前一个节点提供了引用/指针。因此，合并排序的合并操作可以在不为链表留出额外空间的情况下实现。
• 在数组中，我们可以进行随机访问，因为元素在内存中是连续的。假设我们有一个整数（4字节）数组A，A[0]的地址为x，那么要访问A[i]，我们可以直接访问（x+i*4）处的内存。与数组不同，我们不能在链表中进行随机访问。
• 快速排序需要大量此类访问。在链表中，为了访问第i个索引，我们必须将每个节点从头部移动到第i个节点，因为我们没有连续的内存块。因此，快速排序的开销会增加。数据的合并和排序是随机访问。

相关文章：

• 为什么快速排序优于合并排序？
• 了解你的排序算法|集1（编程语言使用的排序武器）
• 迭代合并排序
• 迭代快速排序

幸亏 萨扬·穆霍帕迪亚 为上述条款提供初稿。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。