shellsort.h

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

/*------Shell排序------*/
#ifndef ShellSort_H
#define ShellSort_H
#include <math.h>
void ShellInsert(rectype *R,long n,long h)/*一趟插入排序,h为本趟增量*/
{
	int i,j,k;
	for(i=1;i<=h;i++)  /*i为组号*/
	{              
		for(j=i+h;j<=n;j+=h)   /*每组从第2个记录开始插入*/
		{
			if(R[j].key>=R[j-h].key) continue; /*R[j]大于有序区最后一个记录,则不需要插入*/
		    R[0]=R[j];       /*R[0]保存待插入记录,但不是监哨*/
		    k=j-h;
		    do
			{
			    R[k+h]=R[k];  /*后移记录,继续向前授索*/
				k=k-h; 
			}while(k>0 && R[0].key<R[k].key);
		    R[k+h]=R[0];
		}
	}
}  

void ShellSort(rectype *R,long n)
{
	long i;
	long t=long(ceil(log(n)/log(2)));
	long *d=new long[n];
	d[0]=long(ceil(n/2));
	for(i=1;i<t-1;i++)
		d[i]=long(ceil(d[i-1]/2));
	d[t-1]=1;
	for(i=0;i<t;i++)
		ShellInsert(R,n,d[i]);
}
#endif