merge.c

来自「一个在LINUX下运行的算法比较代码,请下载的朋友 认真分析各行代码」· C语言 代码 · 共 168 行

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

static int count1=0;

static int count2=0;

void quicksort(int *,int *);
void mergelists(int* ,int ,int,int,int);
void quicksort(int* a,int* b)
        {int *p,*q;int v;
        v=*a;p=a;
        q=b;
        while(p<q)

        {while(p<q&&*q>=v){q--;count1++;}

	if(p==q){count1++; break;}

         *p=*q;p++;count1++;

        while(p<q&&*p<=v){p++;count1++;}

	if(p==q){count1++; break;}
        *q=*p;q--;count1++;}

        *p=v;count1++;

       if(a<p-1){count1++; quicksort(a,p-1);}

       if(p+1<b){count1++; quicksort(p+1,b);}
        }



void mergesort(int list[],int first,int last)

	{

 	  int middle;

	if(first<last)

 	  {count2++;

	   middle=(first+last)/2;

	   mergesort(list,first,middle);

	   mergesort(list,middle+1,last);

	   mergelists(list,first,middle,middle+1,last);

	   }

	 }

void mergelists(int list[],int start1,int end1,int start2,int end2)

	{int finalstart;

	 int finalend;

	 finalstart=start1;

	 finalend=end2;

	 int index=1;

	 int i;

	 int result[end1+end2];

	 while((start1<=end1)&&(start2<=end2))

	 {	count2++;

	  if(list[start1]<list[start2])

	   {result[index]=list[start1];

	    start1=start1+1;count2++;}

	  else  

	    {result[index]=list[start2];

	     start2=start2+1;count2++;}

	   index=index+1;}

	 if(start1<=end1)

   	  {count2++;for(i=start1;i<=end1;i++)

	      {result[index]=list[i];

	       index++;}

	  }

	else 

	{count2++;for(i=start2;i<=end2;i++)

	  {result[index]=list[i];

	   index++;}

	}

	index=1;

	for(i=finalstart;i<=finalend;i++)

	  {list[i]=result[index];

	   index=index+1;

	  } 

	}

int main()

	{int i;

	 int n;
	int string[1000];
	int strng1[1000];

	printf("Please input the size :");

	scanf("%d",&n);

	srand((unsigned)time(NULL));

	for(i=0;i<n;i++)

	string[i]=rand()%1000;
	int string1[1000];
	for(i=0;i<n;i++)
		string1[i]=string[i];

	mergesort(string,0,n-1);

	for(i=0;i<n;i++)

	printf(" %d ",string[i]);

	printf("\n");

	int *s;
	s=string1+n-1;

    quicksort(string1,s);	
   for(i=0;i<n;i++)
   printf(" %d ",string1[i]);

	printf("\nThe compared nunber of mergesort is:%d\n",count2);

	printf("\nThe compared number of quicksort is:%d\n",count1);

	return 1;
}