希爾排序

1、希爾排序是對直接插入排序進行改進后增加效率的排序算法。

---- 希爾排序（Shell Sort）：是插入排序的一種。因D.L.Shell于1959年提出而得名。

---- 直接插入排序的效率在某些時候是很高的，比如：

--1）我們的記錄本身就是基本有序的，只需要少量的插入操作，就可以完成整個記錄集的排序工作。

--2）記錄數(shù)比較少的時候。

---- 思想：

??????先取一個小于數(shù)組長度n的整數(shù)d1（一般為n/2）作為第一個增量，把文件的全部記錄分成d1個組，所有距離為d1的倍數(shù)的記錄放在同一個組中。

??????先在各組內(nèi)進行直接插入排序；然后取第二個增量d2<d1(一般為d1/2)，重復上述的分組和排序，直至所取的增量dt=1,即所有記錄放在同一組中

????? 進行直接插入排序為止。

-- 如何將待排序的記錄個數(shù)較少？將原本有大量記錄數(shù)的記錄進行分組，分割成若干個子序列，此時每個子序列待排序的記錄個數(shù)就比較少了，然后

在這些子序列?內(nèi)分別進行直接插入排序，當整個序列都基本有序時，注意只是基本有序時，再對全體記錄進行一次直接插入排序。

-- 所謂的基本有序，就是小的關鍵字基本在前面，大的基本在后面，不大不小的基本在中間，像{2,1,3,6,4,7,5,8,9}這樣的可以稱為基本有序了。

-- 跳躍分割的策略：將相距某個“增量”的記錄組成一個子序列，這樣才能保證在子序列內(nèi)分別進行直接插入排序后得到的結(jié)果是基本有序而不是局部有序。

2、希爾排序算法

例子1：

#includeusing?namespace?std;
#define?dim(x)?(sizeof(x)/sizeof(x[0]))

void?swap(int?*x,int?*y)
{
	int?t?=?*x;
	*x?=?*y;
	*y?=?t;
}
void?ShellSort(int?a[],int?n)
{
	int?k?=?n/2;?//k值代表增量
	while(k>=1)??//當增量k值變化到0，結(jié)束循環(huán)
	{
		for(int?i?=?0;i<n;i++)?//將數(shù)組分成k組，然后對每組進行直接插入排序
		{
			for(int?j?=?i+k;j=k?&&?a[m]<a[m-k])
				{
					swap(&a[m],&a[m-k]);
					m-=k;
				}
			}
		}
		k?=?k/2;
	}
}
void?main()
{
	int?a[]?=?{49,38,65,97,76,13,27};
	ShellSort(a,dim(a));
	for(int?i=0;i<dim(a);i++)
	{
		printf("%d?",a[i]);
	}
	printf("n");
	system("pause");
}

輸出：

例子2：

#define?MaxSize?10	//要排序數(shù)組元素的最大值，可根據(jù)需要修改
typedef?struct?
{
	int?r[MaxSize+1];//用于存儲要排序數(shù)組，r[0]用作哨兵或臨時變量
	int?length;	//用于記錄順序表的長度
}SqList;

void?swap(SqList?*L,int?i,int?j)
{
	int?t?=?L->r[i];
	L->r[i]?=?L->r[j];
	L->r[j]?=?t;
}
void?ShellSort(SqList?*L)
{
	int?i,j;
	int?increment?=?L->length;
	do
	{
		increment?=?increment/3+1;
		for(i=increment+1;ilength;i++)?//具有相同增量的元素分為一組
		{
			if(L->r[i]r[i-increment])
			{
				L->r[0]?=?L->r[i];
				for(j=i-increment;j>0?&&?L->r[j]>L->r[0];j-=increment)
				{
					L->r[j+increment]?=?L->r[j];//記錄后移，查找插入位置
				}
				L->r[j+increment]?=?L->r[0];
			}
		}
	}while(increment>1);

}
int?main()
{
	SqList?*L?=?(SqList*)malloc(sizeof(SqList));
	int?a[MaxSize]?=?{9,1,5,8,3,7,4,6,2,0};
	for(int?i=0;ir[i+1]?=?a[i];
	}
	L->length?=?MaxSize;
	ShellSort(L);
	cout<<"排序后的序列如下："<<endl;
	for(int?i=1;ilength;i++)
	{
		cout<r[i]<<"?";
	}
	cout<<endl;
	system("pause");
	return?0;
}