C++-双向链表的排序操作实现

C++-双向链表的排序操作实现

偏爱自由 发布于 2017-09-30 字数 77 浏览 1339 回复 1

如果要针对一个双向链表head(头结点)进行排序,应该用什么方法比较高效?

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(1

夜无邪 2017-10-15 1 楼

相比较线性表的排序而言,链表排序的内容稍微麻烦一点。就链表的特殊性而言,适合于链表的排序有哪些呢?
(1)插入排序 (适合)
(2)冒泡排序 (适合)
(3)希尔排序 (适合)
(4)选择排序 (适合)
(5)快速排序 (不适合)
(6)合并排序 (不适合)
(7)基数排序 (不适合)
(8)堆排序 (不适合)
其实,一般来说。如果涉及到数据之间的相对关系调配,那么只适合线性排序;如果只是数据内容之间的相互交换,那么这种排序方法也比较适合链表的排序。快速排序、合并排序、堆排序都涉及到了中间值的选取问题,所以不大适合链表排序。
其实如果觉得基本排序太慢的话,可以先把链表中的数据取出来放到线性表中,再用比较快的高级排序,比如快速排序,排完后再放回链表中,这样的算法复杂度也是 O(n log n)