quicksort.h

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

#ifndef QuickSort_H
#define QuickSort_H
long Partition(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];
		if(i==p && i!=q) i=(i+q)/2;
		return i;
}
void QuickSort(rectype *R,long s,long t)
{
	long i;
	if(s>=t) return;  /*只有一个记录或无记录时无需排序*/
	i=Partition(R,s,t);/*对R[s]到R[t]做划分*/
	QuickSort(R,s,i-1);/*递归处理左区间*/
	QuickSort(R,i+1,t);/*递归处理右区间*/
}  
#endif