为什么归并排序对于链表更好？
为什么在对列表进行排序时合并排序被认为是“最佳方法”而不是快速排序？ 我在网上观看的一次讲座中听到了这一点，并在几个网站上看到了这一点。
Why is mergesort considered "the way to go" when sorting lists and not quicksort?
I heard this in a lecture that I watched online, and saw it in a couple of websites.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
快速排序效率的主要来源之一是引用局部性，其中计算机硬件经过优化，以便访问内存位置彼此靠近的内存往往比访问分散在内存中的内存位置要快。快速排序中的分区步骤通常具有出色的局部性，因为它访问前面和后面附近的连续数组元素。因此，快速排序往往比堆排序等其他排序算法表现得更好，尽管它通常执行大致相同数量的比较和交换，因为在堆排序的情况下，访问更加分散。
此外，快速排序通常比其他排序算法快得多，因为它就地操作，无需创建任何辅助数组来保存临时值。与合并排序之类的方法相比，这可能是一个巨大的优势，因为分配和释放辅助数组所需的时间非常明显。就地操作还可以提高快速排序的局部性。
当使用链表时，这些优点都不一定适用。由于链表单元通常分散在整个存储器中，因此访问相邻链表单元没有局部性优势。因此，快速排序的巨大性能优势之一就被耗尽了。同样，就地工作的好处不再适用，因为合并排序的链表算法不需要任何额外的辅助存储空间。
也就是说，快速排序在链表上仍然非常快。合并排序往往更快，因为它更均匀地将列表分成两半，并且每次迭代执行合并的工作量比执行分区步骤的工作量要少。
希望这有帮助！
One of the main sources of efficiency in quicksort is locality of reference, where the computer hardware is optimized so that accessing memory locations that are near one another tends to be faster than accessing memory locations scattered throughout memory. The partitioning step in quicksort typically has excellent locality, since it accesses consecutive array elements near the front and the back. As a result, quicksort tends to perform much better than other sorting algorithms like heapsort even though it often does roughly the same number of comparisons and swaps, since in the case of heapsort the accesses are more scattered.
Additionally, quicksort is typically much faster than other sorting algorithms because it operates in-place, without needing to create any auxiliary arrays to hold temporary values. Compared to something like merge sort, this can be a huge advantage because the time required to allocate and deallocate the auxiliary arrays can be noticeable. Operating in-place also improves quicksort's locality.
When working with linked lists, neither of these advantages necessarily applies. Because linked list cells are often scattered throughout memory, there is no locality bonus to accessing adjacent linked list cells. Consequently, one of quicksort's huge performance advantages is eaten up. Similarly, the benefits of working in-place no longer apply, since merge sort's linked list algorithm doesn't need any extra auxiliary storage space.
That said, quicksort is still very fast on linked lists. Merge sort just tends to be faster because it more evenly splits the lists in half and does less work per iteration to do a merge than to do the partitioning step.
Hope this helps!
find() 的成本对快速排序的危害比合并排序更大。
归并排序对数据执行更多“短程”操作，使其更适合链表，而快速排序更适合随机访问数据结构。
The cost of find() is more harmful to quicksort than mergesort.
Merge sort performs more "short range" operations on the data, making it more suitable for linked lists, whereas quicksort works better with random access data structure.
它的内存效率更高，这就是原因。速度方面，它更慢。链表必须迭代，遍历每个元素才能到达所需的元素，在双向链表的情况下，唯一可以直接访问的元素是第一个元素和最后一个元素，这将进行加法
在列表的第一个和最后一个元素处删除速度更快，否则会更慢，因为它必须迭代每个元素才能到达指定的索引。
另一方面，数组更少，内存效率更高，因为它可以容纳的元素数量是固定的，因此，如果数组中没有使用所有可用空间，那么空间就会被浪费，因为当创建数组后，将分配声明中指定的所选数据类型的元素数量。数组在删除和添加数据时效率较低，因为添加或删除数据后，必须重新排列整个数组。另一方面，数组可以更快地访问元素，准确地说，时间复杂度为 O(1)。
所以总而言之，数组的整体搜索时间更快，删除和添加时间在所有情况下都有 O(m - n + 1) 时间复杂度，其中“m”是数组的大小，“n”是所需的元素指数。链表在第一个和最后一个元素处的添加和删除时间为 O(1)，但时间复杂度最差，因为它必须迭代列表中的每个元素才能找到该元素。链表具有最佳的内存分配，因为链表可以在运行时改变其大小。
信用：https://stackoverflow.com/a/65286515/16587692
It is more memory efficient, that's why. Speed wise, it is slower. Linked lists have to iterate, through each element to get to the desired element, the only elements that can be accessed directly are the first element and the last element, in the case of a doubly linked list and this will make the addition
and deletion faster, at the first and last elements of the list, otherwise it will be slower because it will have to iterate through each element to get to the specified index.
Arrays on the other hand are less, memory efficient, because the number of elements that it can hold is fixed and as a result, if not all of the spaces available in an array are not used, then the space is wasted, because when an array is created, the number of elements of the selected data type specified at the declaration will be allocated. Arrays are less efficient in deleting and adding data, because after the data has been added or deleted, the whole array must be re-arranged. On the other hand, arrays can access elements a lot faster, O(1) time complexity to be exact.
So in conclusion, arrays have faster overall search times, the deletion and addition times have a O(m - n + 1) time complexity in all cases, where "m" is the size of the array and "n" is the desired element index. Linked lists have O(1) addition and deletion times at the first and last element, but what is in between the time complexity is is worst, because it has to iterate through each element of the list, to get to that element. Linked lists have the best memory allocation, because linked list can change its size at runtime.
CREDIT: https://stackoverflow.com/a/65286515/16587692