shellsort.cpp

我们编写的这个程序是为了成功实现希尔排序的程序

#include "stdio.h"
#include<math.h>
void insertionsort(int b[],int n,int st,int in)
{
	int i,j;
	for(i=st+in;i<=n;i=i+in) /*将全部记录存放在b[1]至b[n]中。*/
	{
		b[0]=b[i]; /*把当前要插入的元素b[i]设置为监视哨*/
		j=i-in;    /*从j=i-1开始往前搜索*/
		while(b[0]<b[j]) /*确定当前要插入元素b[i]的插入位置*/
		{
			b[j+in]=b[j];
			j=j-in;
		}
		b[j+in]=b[0];	/*找到位置后插入第i个记录*/
  }
}
void shellsort(int b[],int n)
{
	int increment,passes=(int)(log(n)/log(2))+1,start;
	while(passes>=1)
	{
		increment=(int)pow(2,passes-1);
		for(start=1;start<=increment;start++)
		{
			insertionsort(b,n,start,increment);
		}
		passes=passes-1;
	}
}
int main()
{ 
	int i,n=8;
	int a[9]={0,53,38,47,24,69,5,17,39};
	for(i=1;i<=8;i++)
		printf("%d ",a[i]);
	printf("\nafter shellsorting,the list is:\n");
	shellsort(a,n);
	for(i=1;i<=8;i++)
		printf("%d ",a[i]);
	printf("\n");
	return 0;			
}