quicksort2.h

本文档讲解了几种排序方式的优缺点。包含直接插入、希尔、直接选择、冒泡、快速、堆、二路归并等排序方式。

#ifndef QuickSort2_H
#define QuickSort2_H
long Partition2(rectype *R,long p,long q)/*对无序区R[p]到R[q]划分,返回划分后基准的位置*/
{
	long i,j;
	i=p;
	j=q;
	R[0]=R[i];/*R[0]作辅助量x,存放基准,基准取为无序区第一个记录*/
	while(i<j)
	{
		while(R[j].key>=R[0].key && i<j) j--;/*从右向左扫描*/
		if(i<j) 
		{
			R[i]=R[j];  /*交换R[i]和R[j]*/
		    i++;      
		}
		while(R[i].key<=R[0].key && i<j) i++;
		if(i<j)
		{
			R[j]=R[i];  /*交换R[i]和R[j]*/
			j--;
		}
	}
		R[i]=R[0];
		return i;
}
void QuickSort2(rectype *R,long p,long q)
{
	long *s;
	long i,j,top;
	top=-1;
	s=new long[q-p+1];
	//if(s==NULL) {cout<<"内存不足!";exit(-1);}
	s[++top]=p; /*预入栈*/
	s[++top]=q;
	while(i<j)
	{
		j=s[top--];
		i=s[top--];
		while(i<j)
			p=Partition2(R,i,j);
		if(p-i<j-q) /*先分划前部,后部进栈*/
		{
			s[++top]=p+1;
			s[++top]=j;
			j=p-1;
		}
		else
		{
			s[++top]=i;
			s[++top]=p-1;
			i=p+1;
		}
	}

delete s;
}  
#endif