C语言数据结构与算法之排序总结(二)

void SelectSort(RecordType r[], int length)

{
	int i,j,k;	int n;	RecordType x;    n=length;
	for ( i=1 ; i<= n-1; ++i)  
	{
		k=i;
		for (j=i+1 ; j<= n ; ++j) 
			if (r[j].key < r[k].key ) k=j;
		if ( k!=i) 
		 { 
		     x= r[i];   r[i]= r[k];   r[k]=x;
		}
	}	
}  

void crt_heap(RecordType r[], int length )

{
	int i,n;
    n= length;
	for ( i=n/2; i >= 1; --i)  
		sift(r,i,n);
}

void  sift(RecordType  r[],  int k, int m)

{	RecordType t;	int i,j;	int x;	int finished;
	t= r[k];           	
     x=r[k].key;	i=k;	j=2*i;
	finished=FALSE;
	while( j<=m && !finished  ) 
		{     
		     if (j<m  && r[j].key< r[j+1].key )  j=j+1;   
		     if ( x>= r[j].key)	finished=TRUE;             
		     else 
		     {   r[i] = r[j];  i=j;  j=2*i;	}     
		}
		r[i] =t;           
} 

void  HeapSort(RecordType  r[],int length)
 
{
	int i,n;	RecordType b;
	crt_heap(r, length);	n= length;
	for (  i=n ; i>= 2; --i) 
	{
		b=r[1];      
		r[1]= r[i];
		r[i]=b; 
		sift(r,1,i-1);   
	}
}  

void MergeSort ( RecordType  r[], int n)  
{
	MSort ( r, 1, n, r);
}
void   MSort(RecordType  r1[],  int  low,  int  high,  RecordType  r3[])
 
{
	int mid;   RecordType  r2[20];
	if (low==high)   r3[low]=r1[low];
	else
	{
		mid=(low+high)/2;
        MSort(r1,low, mid, r2);
        MSort(r1,mid+1,high, r2);
        Merge (r2,low,mid,high, r3);
     }
}