單鏈表排序演算法
⑴ 單鏈表的簡單排序
最簡單的選擇排序具體看代碼：
#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)