## STL經典算法集錦<一>之list::sort 算法中使用到的數據結構： ~~~ typedef struct Node* Link; struct Node{ int value; Link next; }; ~~~ 算法代碼： ~~~ //鏈表的歸并 void merge(Link& first,Link& second) { Node newHead; Link temp=&newHead; while(first!=NULL&&second!=NULL) { if(first->value<=second->value) { temp->next=first; first=first->next; } else { temp->next=second; second=second->next; } temp=temp->next; } if(first!=NULL) { while(first!=NULL) { temp->next=first; first=first->next; temp=temp->next; } } else { while(second!=NULL) { temp->next=second; second=second->next; temp=temp->next; } } first=newHead.next; } //聲明為引用類型，以head始終指向鏈表頭而不是原鏈表的頭節點 void mergeSort(Link& head) { //用于存放已序的鏈表的指針數組 Link array[64]; int fill=0; while(head!=NULL) { int i=0; //每次分割出單個節點 Link p=head; head=head->next; p->next=NULL; //向上滾動的條件是鏈表array[i]元素個數滿足2^n //持續向上滾動合并,直至該array[i]中的數據為空不足以持續向上滾動合并 while(i<fill&&array[i]!=NULL) { merge(array[i],p); swap(p,array[i++]); } swap(p,array[i]); if(i==fill) fill++; } //將所有已序鏈表歸并 for(int i=0;i<fill;i++) merge(head,array[i]); } ~~~ 驗證代碼： ~~~ #include <iostream> #include <cstdlib> using namespace std; int main() { int len=20; srand(time(0)); Link head=new Node;//構造鏈表頭 head->value=25; cout<<head->value<<"\t"; Link p=head; //隨機創建一個鏈表 for(int i=0;i<len;i++) { Link next=new Node; p->next=next; next->value=rand()%200; cout<<next->value<<"\t"; p=p->next; } cout<<endl; p->next=NULL; //調用歸并排序 mergeSort(head); //輸出排序后的結果 p=head; while(p!=NULL) { cout<<p->value<<"\t"; p=p->next; } return 0; } ~~~ 單次輸出：