怎么实现单向链表的快速排序
如何实现单向链表的快速排序？
有一个10万结点的单向链表，初始状态时，各结点的关键字大小为无序，现在要使这个链表按从关键字从小到大的顺序排列。
要求：
1. 不使用大量的辅助内存
2. 算法的时间复杂度要小于O(n^2).
结点的数据结构如下：
typedef struct tagNODE
{
int n;//关键字
NODE* next;
}NODE;
使用选择法，自然可以实现排序，并且不需要申请大量内存，但时间复杂度为O(n^2)，请问有没有效率更高的方法？我要源代码。谢谢
------解决方案--------------------
如果是从低向高遍历，整个过程，光找尾指针，就需要o(n^2)的时间负杂度。
~~~~ps:遍历一次单链表是o(n^2)吗？ 有点晕
------解决方案--------------------
用STL中的函数就行了吧,省得自己写了。
------解决方案--------------------
楼主的数据结构为单向链表，是否必须，
如果不是必须，可以用vector <struct node> 来存储
然后使用快速排序算法
或者使用stl的sort（），sort用法可参考msdn
有一个10万结点的单向链表，初始状态时，各结点的关键字大小为无序，现在要使这个链表按从关键字从小到大的顺序排列。
要求：
1. 不使用大量的辅助内存
2. 算法的时间复杂度要小于O(n^2).
结点的数据结构如下：
typedef struct tagNODE
{
int n;//关键字
NODE* next;
}NODE;
使用选择法，自然可以实现排序，并且不需要申请大量内存，但时间复杂度为O(n^2)，请问有没有效率更高的方法？我要源代码。谢谢
------解决方案--------------------
如果是从低向高遍历，整个过程，光找尾指针，就需要o(n^2)的时间负杂度。
~~~~ps:遍历一次单链表是o(n^2)吗？ 有点晕
------解决方案--------------------
用STL中的函数就行了吧,省得自己写了。
------解决方案--------------------
楼主的数据结构为单向链表，是否必须，
如果不是必须，可以用vector <struct node> 来存储
然后使用快速排序算法
或者使用stl的sort（），sort用法可参考msdn