如何通过更改指针的指向来实现单向链表排序,而不是交换数据
希望能写个简单易懂的方法(按从小到大)
比如下面这样的结构吧
typedef struct
{
int data;
struct *next;
}student;
有一个头指针head,指向一个未排好充的链表,请帮忙写一下排序方法
[解决办法]
单链表排序呢:
①,简单的就是冒泡排序,很轻松愉快的 。
过程就是冒泡,需要操作:
1,修改前驱的后继
2,互换当前结点与下一个结点。
需要的变量:pre,cur,next
②,就是快速排序,很快很easy。
过程主要就是Partition函数了,Partition的复杂度是O(n)的,即便这是一个链表。
这个Partition函数需要参考《算法导论》里那种写法,自己去学习。
由于是链表,Partition过程中原本的交换过程变成了插入过程,自己学习之后思考。