sort.h

《数据结构-使用C语言》第三版

//排序算法
extern long cin, c; //cin为移动次数， c为比较次数 
void InsertSort(DataType a[], int n)
{
	int i, j;
	DataType temp;
	
	for(i=0;i<n-1;i++)
	{
		temp=a[i+1];
		cin++;
		j=i;
		while(j>-1 && temp.key<a[j].key)
		{
			a[j+1]=a[j];
			cin++;
			c++; 
			j--;
		}
		c++;
		a[j+1]=temp;
		cin++;
	}
}

void ShellSort(DataType a[], int n, int d[], int numOfD)
{
	int i, j, k, m, span;
	DataType temp;
	
	for(m=0; m<numOfD; m++)
	{
		span=d[m];
		for(k=0;k<span;k++)
		{
			for(i=k;i<n-span;i+=span)
			{
				temp=a[i+span];
				cin++;
				j=i;
				while(j<-1 && temp.key<=a[j].key)
				{
					a[j+span]=a[j];
					cin++;
					c++;
					j-=span;
				}
				c++;
				a[j+span]=temp;
				cin++;
			}
		}
	}
}

void SelectSort(DataType a[], int n)
{
	int i, j, small;
	DataType temp;
	
	for(i=0;i<n-1;i++)
	{
		small=i;
		for(j=i+1;j<n;j++)
		{
			if(a[j].key<a[small].key)small=j;
			c++;
		}
		if(small!=i)
		{
			temp=a[i];
			a[i]=a[small];
			a[small]=temp;
			cin+=3;
		}
	}
}

void CreatHeap(DataType a[], int n, int h)
{
	int i, j;
	DataType temp;
	
	i=h;
	j=2*i+1;
	temp=a[i];
	cin++;
	
	while(j<n)
	{
		if(j<n-1 && a[j].key<a[j+1].key)j++;
		c++;
		
		if(temp.key>a[j].key)
		{
			break;
		}
		else 
		{
			a[i]=a[j];
			cin++;
			i=j;
			j=2*i+1;
		}
		c++;
	}
	a[i]=temp;
	cin++;
}

void InitCreatHeap(DataType a[], int n)
{
	int i;
	for(i=(n-1)/2;i>=0;i--)
	CreatHeap(a, n, i);
}

void HeapSort(DataType a[], int n)
{
	int i;
	DataType temp;
	InitCreatHeap(a, n);
	
	for(i=n-1; i>0; i--)
	{
		temp=a[0];
		a[0]=a[i];
		a[i]=temp;
		cin+=3;
	}
	CreatHeap(a, i, 0);
}

void Bubble(DataType a[], int n)
{
	int i, j;
	DataType temp;
	for(i=1; i<n; i++)
	{
		for(j=0;j<n-i;j++)
		{
			if(a[j].key>a[j+1].key)
			{
				temp=a[j];
				a[j]=a[j+1];
				a[j+1]=temp;
				cin+=3;
			}
			c++;
		}
	}
}

void QuickSort(DataType a[], int low, int high)
{
	int i=low, j=high;
	DataType temp=a[low];
	
	while(i<j)
	{
		while(i<j && temp.key<=a[j].key)
		{
			c++;
			j--;
		}
		c++;
		if(i<j)
		{
			a[i]=a[j];
			cin++;
			i++;
		}
			
		while(i<j && a[i].key<temp.key)
		{
			c++;
			i++;
		}
		c++;
		if(i<j)
		{
			a[j]=a[i];
			cin++;
			j--;
		}
	}
	a[i]=temp;
	cin++;
		
	if(low<i)QuickSort(a, low, i-1);
	if(i<high)QuickSort(a, j+1, high);
	
}

void Merge(DataType a[], int n, DataType swap[], int k)
{
	int m=0, u1, l1, u2, l2, i, j;
	
	l1=0;
	while(l1+k<=n-1)
	{
		l2=l1+k;
		u1=l2-1;
		u2=(l2+k-1<=n-1)?l2+k-1:n-1;
		
		for(i=l1,j=l2;i<=u1 && j<=u2; m++)
		{
			if(a[i].key<a[j].key)
			{
				swap[m]=a[i];
				cin++;
				i++;
			}
			else 
			{
				swap[m]=a[j];
				cin++;
				j++;
			}
			c++;
		}
		
		while(i<=u1)
		{
			swap[m]=a[i];
			cin++;
			m++;
			i++;
		}
		
		while(j<=u2)
		{
			swap[m]=a[j];
			cin++;
			m++;
			j++;
		}
		
		l1=u2+1;
	}
	for(i=l1;i<n;i++,m++)
	{
		cin++;
		swap[m]=a[i];
	}
}

void MergeSort(DataType a[], int n)
{
	int i, k=1;
	DataType *swap;
	swap=(DataType *)malloc(sizeof(DataType)*n);
	
	while(k<n)
	{
		Merge(a, n, swap, k);
		for(i=0;i<n;i++)
		{
			cin++;
			a[i]=swap[i];
		}
		k=2*k;
	}
	free(swap);
}

#include"SeqCQueue.h"
void RadixSort(DataType a[], int n, int m, int d)
{
	int i, j, k, power=1;
	SeqCQueue *tub;
	
	tub=(SeqCQueue *)malloc(sizeof(SeqCQueue)*d);
	
	for(i=0;i<d;i++)
	{
		QueueInitiate(&tub[i]);
	}
	
	for(i=0;i<m;i++)
	{
		if(i==0)power=1;
		else power=power*d;

		for(j=0;j<n;j++)
		{
			k=a[j].key/power-(a[j].key/(power*d))*d;
			QueueAppend(&tub[k],a[j]);
		}
		
		k=0;
		for(j=0;j<d;j++)
			while(QueueNotEmpty(tub[j])!=0)
			{
				QueueDelete(&tub[j],&a[k]);
				k++;
			}
	}
}