1回答

liuyubobobo

2019-12-11

已采纳

不是使用归并排序更好，而是对于链表存储，O(nlogn) 的排序，只能使用归并排序。

这是因为，归并排序的过程，其核心“归并”过程，不需要在数组中随机访问某个索引 i 的数据。只需要相邻的数据不断归并就好。

相较而言，对于快速排序，可以回顾一下快速排序的代码，需要大量的随机访问某个特定索引 i 的数据。可以参考我的代码：https://github.com/liuyubobobo/Play-with-Algorithms/blob/master/03-Sorting-Advance/Course%20Code%20(C%2B%2B)/05-Quick-Sort/main.cpp 20 行，23 行，都需要随机访问某个特定索引 i 的数据。

Leetcode 上的 148 号问题就是对链表的归并排序。我的参考代码：https://github.com/liuyubobobo/Play-Leetcode/blob/master/0148-Sort-List/cpp-0148/main.cpp

继续加油！：）

0

1

Haoming_C

非常感谢！

2019-12-11

共1条回复