naturesort_list.cpp

链表实现快速排序, 链表实现快速排序,

#include<stdio.h>
#include<stdlib.h>

struct cnode 
{ 
    int  num; 
    struct cnode *next; 

}*head,*tail; 

int partition(cnode *,cnode *[]);
cnode* MergeSort(cnode *,int,cnode *[]);
cnode* MergePass(cnode *,int,cnode *[]);
cnode* Merge(cnode *,cnode *);

void main() 
{ 
   int tc; 
   struct cnode *tp; 
   head=tail=0;
   printf("Enter the array(-1 to end):\n");
   scanf("%d",&tc);
   while(tc!=-1) 
   { 
      tp=(struct cnode*)malloc(sizeof(struct cnode)); 
      tp->num=tc; 
      tp->next=0; 
      if(head==0) 
      head=tp; 
      else 
         tail->next=tp; 
      tail=tp; 
      scanf("%d",&tc);
   } 
   //打印用户输入的序列
   printf("\nYou have entered:\n"); 
   tp=head; 
   while(tp!=0) 
   { 
        printf("%4d",tp->num); 
        tp=tp->next; 
   } 
   printf("\nAfter sorting:\n");
   struct cnode *part[50];
   int part_no=partition(head,part);

   head=MergeSort(head,part_no,part);
   tp=head; 
   while(tp!=0) 
   { 
        printf("%4d",tp->num); 
        tp=tp->next; 
   } 
   printf("\n");
}

//用part结构数组来存储除了第一个子序列外其他子序列的开始位置
//返回子序列个数
int partition(cnode *head,cnode *part[])
{
	int i=0;
	cnode *p=head;
	cnode *q=p;
	while(p->next!=NULL)
	{
		if(p->num > p->next->num)
		{
			part[i++]=p->next;
			q=p;
            p=p->next;
			q->next=NULL;
		}
		else p=p->next;
	}
	return i+1;
}

//当子序列个数大于1时继续排列，排列后重新计算子序列个数，判断是否重新排列
//直至子序列个数为1，即已排好
//返回序列头结点
cnode* MergeSort(cnode *head,int part_no,cnode *part[])
{
	while(part_no>1)
	{
		head=MergePass(head,part_no,part);

		if(part_no%2==0)
			part_no=part_no/2;
		else part_no=part_no/2+1;
	}
	    return head;
}

//根据part数组存储的内容，调用Merge方法进行排序，重新设置part结构数组
cnode* MergePass(cnode *head,int part_no,cnode *part[])
{
	int i=0,j=0;
	for(i=0;i<part_no;i+=2)
	{
		if(i==0)
			head=Merge(head,part[0]);
		else {
			if(i+1<part_no)
			   part[j++]=Merge(part[i-1],part[i]);
		}
	}
	part[j]=part[part_no-2];
	return head;
}

//对给定的两个子序列的头结点，将两个子序列进行排序
//链成一个新的链表，并返回起始结点
cnode* Merge(cnode *fhead,cnode *shead)
{
	cnode *p,*q,*r;
	cnode *rhead;
	p=fhead;
	q=shead;

	if(p->num<=q->num)
	{
		rhead=p;
		p=p->next;
	}
	else{
		rhead=q;
        q=q->next;
	}
	r=rhead;

	while(p!=NULL&&q!=NULL)
	{
		if(p->num<=q->num)
		{
			r->next=p;
			r=p;
			p=p->next;
		}
		else {
			r->next=q;
			r=q;
			q=q->next;
		}
	}

	if(p==NULL)
		r->next=q;
	if(q==NULL)
		r->next=p;

	return rhead;
}