单链表排序算法
⑴ 单链表的简单排序
最简单的选择排序具体看代码：
#include<cstdio>
#include<cstdlib>
#include<ctime>
structnode{
intval;
node*next;
node(intv):val(v),next(NULL){}
};
//从小到大，最简单的选择排序
node*linklist_sort(node*head){
node*nhead=newnode(0);
while(true){
node*temp=head,*maxpre=head;
for(;temp->next;temp=temp->next){
if(temp->next->val>maxpre->next->val){
maxpre=temp;
}
}
if(temp==head)break;
temp=maxpre->next;
maxpre->next=temp->next;
temp->next=nhead->next;
nhead->next=temp;
}
head->next=nhead->next;
returnhead;
}
voidtraval(node*head){//遍历单链表
while(head->next){
printf("%d",head->next->val);
head=head->next;
}
printf(" ");
}
intmain(){
srand(time(NULL));
node*head=newnode(0);
for(inti=0;i<10;i++){
node*t=newnode(rand()%1000);
t->next=head->next;
head->next=t;
}
traval(head);
head=linklist_sort(head);
traval(head);
return0;
}
⑵ 单链表排序算法分析
for(q=p->next;q;q=q->next) 因为每一步都要从p开始，与后面所有结构体进行比较，所以q作为这一次比较的指针，下次又从p开始，直至p为空
small=q; /*执行这句之后又回到for(q=p->next;q;q=q->next） 直到本次比较结束
temp=p->data;
p->data=small->data; 把本次找到的最小值与头结点值进行交换,还差一句:small->data=temp;
⑶ 对单链表中的数据进行排序，用哪种算法比较好
typedef struct __LINK
{
int data;
struct __LINK *next;
} LinkNode_t;
//冒泡排序单连表, 交换值方式
bool LinkSort( LinkNode_t* &head )
{
assert( head != NULL );
bool change = true;
LinkNode_t* p = head;
LinkNode_t* pStop = head->next;
int ifirst = 0;
while ( pStop && pStop->next )
{
pStop = pStop->next;
}
LinkNode_t* pFlag = head;
while ( change )
{
change = false;
for ( p = head->next; p != pStop; p = p->next )
{
if ( p->data < p->next->data )
{
int value = p->data;
p->data = p->next->data;
p->next->data = value;
change = true;
}
if ( p->next == pStop ) pFlag = p;
}
pStop = pFlag;
}
return true;
}
⑷ 以单链表为存储结构，编写简单选择排序算法（需预先创建符合要求的单链表）
选择排序：从头至尾扫描序列，找出最小的一个元素，和第一个元素交换，接着从剩下的元素中继续这种选择和交换方式，最终得到一个有序序列。
出这题的人是个坑货，链表交换很麻烦。
每次遍历找最小值时候 还要用一个指针定位到它前面一个， 才好交换。
⑸ 单链表的直接插入排序的算法。问题
一开始head->next=NULL;与q=head->next;表示将头指针与后面的链表完全断开，然后p就是后面链表的第一个结点，第一个while就是用来判断后面的那个链表是否有剩，然后q表示head的下一个结点，因为第一次操作head下一个是空的，所以第二个while跳出来，后面链表首结点下一个指向head的下一个即空，head下一个变成后面链表首结点，总的说就是把后面链表的首结点插到head的后面，之后p=pre来使后面链表首结点向后移。后面的操作也是一样，不过经过第一轮操作后，head后面已经有了结点，所以第二轮操作需要第二个while来控制应该插在哪里
⑹ 单链表的排序算法，哪位大师麻烦您说一哈，感激不尽！
这个比较恶心，最好使用插入排序的方式，效率稍微高点。先对数组排序实现一个插入排序，代码不多，可以写一个。然后就按照那种思想，将链表节点拿出来插入到正确位置。
后来是刷题刷到的一个题目吧，好像是使用快慢指针的方式，采用归并排序，性能算nlgn吧。这个算法分为以下三步，
利用快慢指针找到链表的中间节点，O(n/2)
分别执行n/2长度的归并算法，2*T(n/2)
对两段归并的结果进行merge，O(n)
T(n) = O(n/2) + 2*T(n/2) + O(n)
上面的这个公式的时间复杂度是O(n*lgn)