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<<"	";
                Link p=head;
		//随机创建一个链表
		for(int i=0;i<len;i++)
		{
				Link next=new Node;
				p->next=next;  
				next->value=rand()%200;
				cout<<next->value<<"	";
				p=p->next;
		}
		cout<<endl;
		p->next=NULL;
		//调用归并排序
		mergeSort(head);
		//输出排序后的结果
		p=head;
		while(p!=NULL)
		{
				cout<<p->value<<"	";
				p=p->next;
		}
		return 0;
}

单次输出：