## 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; } ~~~ 单次输出：