不理解自底向上的归并排序为何适用于链表的排序
来源：3-4 自底向上的归并排序算法
精慕门8491163
2019-06-01
关于自底向上的归并排序中“由于排序的过程，没有用到通过数组的索引获取值的特性，因此适合用于链表的排序”
_merge函数中，不也是要通过索引访问值么，是不是本质上是因为这里面通过i,j，k来访问元素的特性，很适合于链表的节点访问？？
写回答
1回答
-
_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
加油！：）
032021-07-02
相似问题