; MUST add an "getch"!!*/
{
clock_t start,end;
start=clock();
(*LS)=shellsort(L);
end=clock();
*timeshell=(end-start)/CLK_TCK;
printf("\nSHELLSORT COST TIME :%f SECONDS.",*timeshell);
printf("Compare %d times.Shfit %d times.\n",compCount,shiftCount);
}
int Partition(list * pL,int low,int high)
{
int pivotkey;
pL->key[0]=pL->key[low];shiftCount++;
pivotkey=pL->key[low];shiftCount++;
while(low<high)
{
compCount++;
while(low<high && pivotkey<=(pL->key[high]))
{compCount++;compCount++; --high;}
pL->key[low]=pL->key[high];shiftCount++;
while(low<high && (pL->key[low])<=pivotkey)
{compCount++;compCount++; ++low;}
pL->key[high]=pL->key[low];shiftCount++;
}
pL->key[low]=pL->key[0];shiftCount++;
return low;
}/*Partition*/
void QSort(list * pL,int low,int high)
{
int pivotloc;
if(low<high)
{
compCount++;
pivotloc=Partition(pL,low,high);
QSort(pL,low,pivotloc-1);
QSort(pL,pivotloc+1,high);
}
}/*QSort*/
list QuickSort(list pL)
{
compCount=shiftCount=0;
QSort(&pL,1,pL.length);
return pL;
}/*QuickSort*/
void quick(list L,list *LQ,float *timequick)/*MUST add an "getch"!!*/
{
clock_t start,end;
start=clock();
(*LQ)=QuickSort(L);
end=clock();
*timequick=(end-start)/CLK_TCK;
printf("\nQUICKSORT COST TIME :%f SECONDS.",*timequick);
printf("Compare %d times.Shfit %d times.\n",compCount,shiftCount);
}
void sift(list L,int l,int m)
{
int i,j,x;
i=l;
j=2*i;
x=L.key[i];
while (j<=m)
{
compCount++;
if(j<m && L.key[j]<L.key[j+1]) {j++;compCount++;compCount++;}
if(x<L.key[j])
{
compCount++;
L.key[i]=L.key[j];shiftCount++;
i=j;shiftCount++;
j=2*i;
}
else j=m+1;
}
L.key[i]=x;shiftCount++;
}
list heapsort(list L)
{
int i,w;
compCount=shiftCount=0;
for (i=L.length/2;i>=1;i--) {sift(L,i,L.length);compCount++;}
for (i=L.length;i>=2;i--)
{
compCount++;
w=L.key[i];shiftCount++;
L.key[i]=L.key[1];shiftCount++;
L.key[1]=w;shiftCount++;
sift(L,i-1,1);
}
return L;
}
void heap(list L,list *LH,float *timeheap)
{
clock_t start,end;
start=clock();
(*LH)=heapsort(L);
end=clock();
*timeheap=(end-start)/CLK_TCK;
printf("\nHEAPSORT COST TIME :%f SECONDS.",*timeheap);
printf("Compare %d times.Shfit %d times.\n",compCount,shiftCount);
}
void Merge(int source[],int result[],int size,int n)
{
int lb1,lb2,ub1,ub2,p,i,j;
lb1=0;
p=0;
while((lb1+size)<n)
{
compCount++;
lb2=lb1+size;
ub1=lb2-1;
if((lb2+size-1)>n)
{ ub2=n-1; compCount++; shiftCount++;}
else
{ub2=lb2+size-1; compCount++; shiftCount++;}
i=lb1;
j=lb2;
while((i<=ub1)&&(j<=ub2))
{
compCount++;compCount++;
if(source[i]<=source[j])
{result[p++]=source[i++]; shiftCount++; compCount++;}
else
{result[p++]=source[j++]; shiftCount++; compCount++;}
}
while(i<=ub1)
{result[p++]=source[i++]; shiftCount++; compCount++;}
while(j<=ub2)
{result[p++]=source[j++]; shiftCount++; compCount++;}
lb1=ub2+1;
}
i=lb1;
while(p<n)
{compCount++; result[p++]=source[i++];shiftCount++;}
}
void Mergesort(list *L)
{
int n=(*L).length;
int s=1;
int *temp=(int *)malloc(n*sizeof(int));
compCount=shiftCount=0;
if (temp==NULL)
{
printf("out of memory");
return;
}
while(s<n)
{
compCount++;
Merge((*L).key,temp,s,n);
s*=2;
Merge(temp,(*L).key,s,n);
s*=2;
}
compCount++;
}
void domerge(list L,list *LM,float *timemerge)/*MUST add an "getch"!!*/
{
clock_t 上一页 [1] [2] [3] [4] 下一页 |
