排序链接列表的最佳方法是什么？

Question

在[C/C++]中对链接列表进行排序的最佳算法是什么？

Answer 1

合并排序适用于排序链表.这里有一些细节.这里有示例C代码.

为什么适合？好吧,简单来说,mergesort的主要组件 - 排序子序列的合并 - 可以在两个链表上轻松完成,因为它只需要比较头元素,因此它不需要数组的随机访问.

此外,这里有一篇名为"链接列表排序算法的比较研究"的文章,您可能会感兴趣.

Answer 2

合并排序.

更好的是,只需使用std::list它的sort()方法.