请教如何实现链表中按关键字排序

zerix

有一结构体实现的单链表，如何实现按结构体中一项或2项的关系实现排序。

有没有开源的算法或者demo程序或者提供原理思路等？

谢谢指教了。。

gawk

用qsort试试

shan_ghost

适合单链表的排序方法，可能只有归并一个……

比如，3->4->9->8->6，第一步先把它看作5个单元素子链表两两归并，得3->4、8->9、6三个有序子链表；然后在这三个子链表上反复执行上述操作，即可得到最终结果。


也可以用一个数组记下每个节点的指针，然后把这个数组扔给qsort完成排序，最后再根据数组重新生成有序链表——这个办法需要自己实现的代码更少，更不易出错。

[ 本帖最后由 shan_ghost 于 2009-2-19 17:13 编辑 ]

cugb_cat

原帖由 gawk 于 2009-2-19 16:45 发表
用qsort试试

qsort只能是连续的。

gawk

原帖由 cugb_cat 于 2009-2-19 16:58 发表

qsort只能是连续的。

呵呵，所以说试试

gawk

不过也可以构造个指针数组，然后用qsort排完序，然后在从新构造链表，O(∩_∩)O~

zerix

有没有相关例子的源码的。。

wangqi0021

原帖由 gawk 于 2009-2-19 17:01 发表

呵呵，所以说试试

这样会造成一个隐藏的 bug吧。  你不能保证list里边挂的内存是连续的

langue

哎呀，quick sort 只是一种算法嘛，当标准库无法满足需求的时候，就需要自己动手写了。
其实就是编写排序算法的实现，具体用哪个算法，按照什么字段排列，都得你自己考虑。

gawk

原帖由 wangqi0021 于 2009-2-19 18:04 发表



这样会造成一个隐藏的 bug吧。  你不能保证list里边挂的内存是连续的

我指的试试，是想他结合qsort往指针数组上构造