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

为什么是快速排序首选数组？

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

数组的递归快速排序。

数组的迭代快速排序。

数组的递归合并排序

数组的迭代合并排序

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

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

下面是Quicksort和Mergesort用于单链和双链列表的实现。

快速排序双重链接列表

快速排序单链接列表

合并单链接列表的排序

合并双链表的排序

的情况下链表情况不同主要是由于数组和链表的内存分配不同。与数组不同, 链接列表节点在内存中可能不相邻。
与数组不同, 在链表, 如果我们给定上一个节点的引用/指针, 则可以在O(1)额外空间和O(1)时间的中间插入项目。因此, 可以实现合并排序的合并操作而不必为链接列表增加空间。
在数组中, 由于元素在内存中是连续的, 因此我们可以进行随机访问。假设我们有一个整数(4字节)数组A, 并且将A [0]的地址设为x, 然后访问A [i], 我们可以直接访问(x + i * 4)处的内存。与数组不同, 我们不能在链表中进行随机访问。
快速排序需要很多此类访问权限。在链接列表中, 要访问第i个索引, 由于没有连续的内存块, 我们必须将每个节点从头到第i个节点。因此, 用于快速分类的开销增加了。合并排序顺序访问数据, 并且对随机访问的需求低。

谢谢萨彦(Sayan Mukhopadhyay)提供上述文章的初稿。如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。