shellsort2.h

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

/*------Shell排序2------*/
#ifndef ShellSort2_H
#define ShellSort2_H
#include <math.h>
void ShellInsert2(rectype *R,long n,long h)/*一趟插入排序,h为本趟增量*/
{
	int i,j,k;
	for(i=1;i<=h;i++)  /*i为组号*/
	{              
		for(j=n-i-h;j>=1;j-=h)   /*每组右起从第2个记录开始插入,它的下标为n-i-h*/
		{
			if(R[j].key<=R[j+h].key) continue;/*R[j]小于有序区最后一个记录,则不需要插入*/
			R[n-i+h]=R[j];      /*监视哨*/
			k=j+h;              /*待插入记录的后一个记录*/
			while(R[n-i+h].key>R[k].key)/*查找正确的插入位置*/
			{
				R[k-h]=R[k];            /*前移记录*/
				k=k+h;                  /*向后搜索*/
			}
			R[k-h]=R[n-i+h];            /*插入R[j]*/
		}
	}  
}
 
void ShellSort2(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++)
		ShellInsert2(R,n,d[i]);
}
#endif