一、 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->datadata) { 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; } 

while(r!=e2->next) { p->next=r;p=r; r=r->next; } }//LinkedList_Merge