内部排序比较.cpp

各种排序方法的比较。有冒泡法

//********************************************************************
//建非空表函数1
//设所建的表有n个元素

void  newlist(sqlist &l,int n)
{ 
	int i;
	
	initlist(l,n+1);  //建空表
    
	for(i=1;i<=n;i++)//逐一输入数据结点建表
	{
		cout<<"请输入建表元素："<<endl;
 		cin>>l.elem[i];	
	}
     
	l.length = n;
}


//********************************************************************
//随机函数创建线性表

void Filelist(char filename[])
{
	
	int *array=new int[maxSize];
	int j;
		
	srand( (unsigned)time( NULL ) );
    for( j=0;j<maxSize;j++ )
    {
			array[j]=rand( ) % 32767- rand( ) % 32767;
			if(array[j]<0)
				array[j]=-array[j];
    }	

	fstream listfile;
	
	listfile.open(filename,ios::binary|ios::out);
	if(listfile.fail())
	{
		cout<<"文件打开失败!"<<endl;
		exit(0);
	}
   	listfile.write((char*)array,maxSize*sizeof(int));
	
	listfile.close();
	delete[] array;

}
void Newsqlist(sqlist &list,char filename[],int sum)
{

	fstream listfile;
	
	listfile.open(filename,ios::binary|ios::in);
	if(listfile.fail())
	{
		cout<<"文件打开失败!"<<endl;
		exit(0);
	}
	
	for(int i=1;i<=sum&&!listfile.eof();i++)
	{
		listfile.read((char*)&list.elem[i],sizeof(int));
	}
	
	listfile.close();
	
	list.length=sum;

}
void Newsllist(SlList &list,char filename[],int sum)
{
	fstream listfile;
	list.keynum=5;
	list.length=0;
	
	listfile.open(filename,ios::binary|ios::in);
	if(listfile.fail())
	{
		cout<<"文件打开失败!"<<endl;
		exit(0);
	}

	for(int i=1;i<=sum&&!listfile.eof();i++)
	{
		listfile.read((char*)&list.r[i].elem,sizeof(int));
		FindKey(list,i);
		list.length++;
	}

	listfile.close();

}
void saveStyleSum(char filename[],int sum)
{
	fstream listfile;
	listfile.open(filename,ios::out|ios::app);
	
	if(listfile.fail())
	{
		cout<<"文件打开失败!"<<endl;
		exit(0);
	}
	listfile<<setw(5)<<sum;
	listfile.close();
}
void saveStyleHead(char filename[])
{
	fstream listfile;
	listfile.open(filename,ios::out|ios::app);
	
	if(listfile.fail())
	{
		cout<<"文件打开失败!"<<endl;
		exit(0);
	}
	listfile<<setw(6)<<"数目"<<setw(8)<<"冒泡"<<setw(10)<<"直接插入"<<setw(10)<<"折半插入";
	listfile<<setw(6)<<"希尔"<<setw(8)<<"快速"<<setw(7)<<"选择"<<setw(6)<<"堆";
	listfile<<setw(9)<<"归并"<<setw(8)<<"基数"<<endl;
	listfile.close();
}


void saveResult(int t1,int t2,int i,char filename[])
{
	fstream listfile;
	listfile.open(filename,ios::out|ios::app);
	
	if(listfile.fail())
	{
		cout<<"文件打开失败!"<<endl;
		exit(0);
	}
	if(i==9)
	{
		listfile<<setw(8)<<(t2-t1)<<endl;
	}
	else
		listfile<<setw(8)<<(t2-t1);
	listfile.close();
}





//*******************************************************************

//***********************    排序算法     ***************************

//*******************************************************************
//冒泡排序
void BubbleSort(sqlist &l)
{ 
	int q;
	int i;

	for(i=1;i<=l.length;i++)
		for(int j=1;j<=l.length-i;j++)
		{
			if(l.elem[j]>l.elem[j+1])
			{
				q=l.elem[j];//交换l.elem[j]和l.elem[j+1]的位置
				l.elem[j]=l.elem[j+1];
				l.elem[j+1]=q;
			}
		}		
}

//********************************************************************
//直接插入排序
void InsertSort(sqlist &l)
{
	int q,sub;
	
	for(int i=2;i<=l.length;i++)
		for(int j=1;j<i;j++)
		{
			q=i;
			if(l.elem[i]<l.elem[j])//查找插入位置
			{
				sub=l.elem[i];
				while(j<q)	//插入l.elem[i];
				{
					l.elem[q]=l.elem[q-1];
					q--;
				}
				l.elem[j]=sub;
				break;
			}
			
		}
	
}

//********************************************************************
//折半插入排序
void BInsertSort(sqlist &l)
{
	int q,sub,low,high,mid;

	for(int i=2;i<=l.length;i++)
	{
		sub=l.elem[i];
		low=1;
		high=i-1;

		while(low<=high)//折半查找插入位置
		{
			mid=(low+high)/2;
			
			if(sub<l.elem[mid])
				high=mid-1;
			else if(sub==l.elem[mid])
			{
				high=mid-1;
				low=mid+1;
			}
			else
				low=mid+1;
		}
		q=i;
		while(high+1<q)
		{
			l.elem[q]=l.elem[q-1];
			q--;
		}
		l.elem[high+1]=sub;
	}
}
//********************************************************************
//希尔排序
void ShellInsert(sqlist &l,int dk)
{
	int sub;
	for(int i=dk;i<=l.length;i++)
	{
		if(l.elem[i]<l.elem[i-dk])
		{
			sub=l.elem[i];
			for(int j=i-dk;j>0&&sub<l.elem[j];j=j-dk)
			{
				l.elem[j+dk]=l.elem[j];
			}
			l.elem[j+dk]=sub;
		}
	}
}

void ShellSort(sqlist &l)
{
	int gap=l.length/2;
	while(gap)
	{
		ShellInsert(l,gap);
		gap=(gap==2?1:(gap/2));//取间隔
	}
}


//********************************************************************
//快速排序
int Partition(sqlist &l,int low,int high)
{
	int pivotkey=l.elem[low];

	while(low<high)
	{
		while((l.elem[high]>=pivotkey)&&(low<high))high--;
		l.elem[low]=l.elem[high];
		while((l.elem[low]<=pivotkey)&&(low<high))low++;
		l.elem[high]=l.elem[low];
	}
	l.elem[low]=pivotkey;
	return low; 
	
}

void QSort(sqlist &l,int low,int high)
{
	int pivotloc;
	if(low<high)
	{
		pivotloc=Partition(l,low,high);
		QSort(l,low,pivotloc-1);
		QSort(l,pivotloc+1,high);
	}
	
}
//********************************************************************
//选择排序
void SelectSort(sqlist &l)
{
	int sub,position;
	for(int i=1;i<l.length;i++)
	{
		sub=l.elem[i];
		position=i;
		for(int j=i+1;j<=l.length;j++)
		{
		
			if(l.elem[j]<sub)
			{
				sub=l.elem[j];
				position=j;
			}
		}
		l.elem[position]=l.elem[i];
		l.elem[i]=sub;
	}
}

//********************************************************************
//堆排序

void HeapAdjust(HeapType &h,int s,int m)	//本函数为调h.elem[s],使堆成为大顶堆
{											//h.elem[s...m]中除h.elem[s]之外均满足队的定义
	int rc=h.elem[s];
	for(int j=2*s;j<=m;j*=2)
	{
		if(j<m&&(h.elem[j]<h.elem[j+1]))j++;//找最大的孩子节点
		if(rc>=h.elem[j])break;
		h.elem[s]=h.elem[j];
		s=j;
	}
	h.elem[s]=rc;
}
void HeapSort(HeapType &h)
{
	int sub;
	for(int i=(h.length)/2;i>0;i--) //调整为大顶堆
		HeapAdjust(h,i,h.length);
	for(i=h.length;i>1;i--)//将大顶堆顶端元素派到依次排到相应位置
	{
		sub=h.elem[1];
		h.elem[1]=h.elem[i];
		h.elem[i]=sub;
		HeapAdjust(h,1,i-1);//重新调整为大顶堆
	}
}

//********************************************************************
//归并排序

void merge(sqlist sr,sqlist &tr,int l,int m,int n)
{
	int i=l,j=m+1,k=l;
	for(i,j;(i<=m)&&(j<=n);k++)
	{
		if(sr.elem[i]<sr.elem[j])
		{
			tr.elem[k]=sr.elem[i];
			i++;
		}
		else
		{
			tr.elem[k]=sr.elem[j];
			j++;
		}
	}
	if(i<=m)
	{
		for(k;k<=n;k++)
		{
			tr.elem[k]=sr.elem[i++];
		}
	}
	if(j<=n)
	{
		for(k;k<=n;k++)
		{
			tr.elem[k]=sr.elem[j++];
		}
	}
}

void MSort(sqlist sr,sqlist &tr1,int s,int t)
{
	int m;
	if(s==t)tr1.elem[s]=sr.elem[s];
	else
	{
		sqlist tr2;
		initlist(tr2,maxSize);
		m=(s+t)/2;
		MSort(sr,tr2,s,m);
		MSort(sr,tr2,m+1,t);
		merge(tr2,tr1,s,m,t);
	}
}

void MergeSort(sqlist &l)
{
	MSort(l,l,1,l.length);
}

//********************************************************************
//基数排序
void Distribute(SlList &l,int i,arrayPtr &f,arrayPtr &e)
{
	int j,p;
	for(j=0;j<radix;j++)
		f[j]=0; //给f指针数组置零
	for(p=l.r[0].next;p;p=l.r[p].next)
	{
		j=l.r[p].keys[i];
		if(!f[j])
			f[j]=p;
		else 
			l.r[e[j]].next=p;
		e[j]=p;
	}
}

void Collect(SlList &l,int i,arrayPtr f,arrayPtr e)
{
	int j=0,t;
	while(!f[j])j++;
	l.r[0].next=f[j];
	t=e[j];
	while(j<radix)
	{
		for(j=j+1;j<radix;j++)
		{
			if(f[j]!=0)
			{
				 l.r[t].next=f[j]; 
				 t=e[j];
			}
		}
	}
	l.r[t].next=0;
}

void RadixSort(SlList &l)
{
	arrayPtr f,e;
	int i;
	
	for(i=0;i<l.length;i++)//创建静态链表
	{
		l.r[i].next=i+1;
	}
	l.r[l.length].next=0;
	for(i=0;i<l.keynum;i++)
	{
		Distribute(l,i,f,e);
		Collect(l,i,f,e);
	}
}