Shell排序

Shell排序
希尔排序是一种插入排序算法，它出自D.L.Shell，因此而得名。Shell排序又称作缩小增量排序。Shell排序的执行时间依赖于增量序列。
先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插入排序;然后，取第二个增量d2该方法实质上是一种分组插入方法。
增量序列的选择
Shell排序的执行时间依赖于增量序列。
好的增量序列的共同特征:
① 最后一个增量必须为1;
② 应该尽量避免序列中的值(尤其是相邻的值)互为倍数的情况。
有人通过大量的实验，给出了目前较好的结果:当n较大时，比较和移动的次数约在n到1.6n之间。
希尔排序的时间性能优于直接插入排序的原因:
①当文件初态基本有序时直接插入排序所需的比较和移动次数均较少。
②当n值较小时，n和n^2的差别也较小，即直接插入排序的最好时间复杂度O(n)和最坏时间复杂度0(n^2)差别不大。
③在希尔排序开始时增量较大，分组较多，每组的记录数目少，故各组内直接插入较快，后来增量di逐渐缩小，分组数逐渐减少，而各组的记录数目逐渐增多，但由于已经按di-1作为距离排过序，使文件较接近于有序状态，所以新的一趟排序过程也较快。
因此，希尔排序在效率上较直接插入排序有较大的改进。
希尔排序是不稳定的。

#include
using namespace std;
void shell(int a[],int n)
{
	int temp;
	for(int step=n/2; step>0;step=step/2){
		for(int k=0;k=0&&a[j]>temp;j=j-step)
					{
						a[j+step]=a[j];
					}
					a[j+step]=temp;
				}
			}
		}
	}
}
void print(int a[],int n)
{
	for(int i=0;i>n;
	for (int i=0;i>a[i];
	}
	shell(a,n);//排序
	print(a,n);//输出
}