链表排序

用什么算法好？
目前用的算法是快速排序
在每次递归中都需要遍历链表来查找节点。
这样的话平均情况也没办法达到O(nlgn)了。
堆排序怎么样？
感谢吧友。

或者有什么更好的算法吗？

2025-03-27 20:36广告

堆排吧，毕竟顺序存储。

其实把链表中的元素复制到一个可以随机存取的容器中再排序，然后再复制回去，都比链表直接排序快

我看到 merge sort 也有 nlogn 的，但我没有深究是怎样实现

今天试了试，循环双链表排序，用的快排，刚好O(nlgn)。 firebug显示用时从5.23s降到了405ms。可以接受了！

c++有容器。。速度很快。

楼主如果只侧重排序的结果可以考虑一下用，二叉排序树，平衡树，红黑树

下载贴吧APP
看高清直播、视频！

分享到: