不理解自底向上的归并排序为何适用于链表的排序

Question

关于自底向上的归并排序中“由于排序的过程，没有用到通过数组的索引获取值的特性，因此适合用于链表的排序”

_merge函数中，不也是要通过索引访问值么，是不是本质上是因为这里面通过i,j，k来访问元素的特性，很适合于链表的节点访问？？

Answer 1

liuyubobobo 2019-06-02 02:27:57

_merge通过索引访问值，这是因为我们的底层数据结构是数组。

但仔细观察，你就会发现，_merge函数不会跳跃访问元素（这是和快排本质不同的地方）。我们只需要顺次访问元素就可以。而链表，相当于只提供顺次访问的功能。所以，归并排序的思路可以很容易地应用于链表。

在这里，我建议你感兴趣，尝试实现一个链表的merge操作，再体会一下。

Leetcode 21号问题就是这个问题：https://leetcode.com/problems/merge-two-sorted-lists/

我的参考代码：https://github.com/liuyubobobo/Play-Leetcode/tree/master/0021-Merge-Two-Sorted-Lists/cpp-0021

加油！：）

• BYMS #1

  老师，为什么快速排序是跳跃访问元素的？哪里跳跃了？

• liuyubobobo 回复 BYMS #2

  随机化标定点是跳跃；不管是哪种 partition 实现的快排，左右两边的元素做 swap，也是跳跃。

• BYMS 回复 liuyubobobo #3

  回复 liuyubobobo谢谢老师