一、 2-路归并排序的另一策略是，先对待排序序列扫描一遍，找出并划分为若干个最大有
序子列，将这些子列作为初始归并段，试写一个算法在链表结构上实现这一策略。
void LinkedList_Merge_Sort2(LinkedList &L)//初始归并段为最大有序子序列的归并排序,采
用链表存储结构
{
LNode *end[MAXSIZE]; //设立一个数组来存储各有序子序列的尾指针
for(p=L->next->next,i=0;p;p=p->next) //求各有序子序列的尾指针
if(!p->next||p->data>p->next->data) end[i++]=p;
while(end[0]->next) //当不止一个子序列时进行两两归并
{
j=0;k=0; //j:当前子序列尾指针存储位置;k:归并后的子序列尾指针存储位置
for(p=L->next,e2=p;p->next;p=e2) //两两归并所有子序列
{
e1=end[j];e2=end[j+1]; //确定两个子序列
if(e1->next) LinkedList_Merge(L,p,e1,e2); //归并
end[k++]=e2; //用新序列的尾指针取代原来的尾指针
j+=2; //转到后面两个子序列
}
}//while
}//LinkedList_Merge_Sort2
void LinkedList_Merge(LinkedList &L,LNode *p,LNode *e1,LNode *e2)//对链表上的子序列进
行归并,第一个子序列是从 p->next 到 e1,第二个是从 e1->next 到 e2
{
q=p->next;r=e1->next;
while(q!=e1->next&&r!=e2->next)
{
if(q->data<r->data)
{
p->next=q;p=q;
q=q->next;
}
else
{
p->next=r;p=r;
r=r->next;
}
}//while
while(q!=e1->next)
{
p->next=q;p=q;
q=q->next;
