希尔排序

希尔排序(Shell Sort)是插入排序的一种。是针对直接插入排序算法的改进。该方法又称缩小增量排序，因DL．Shell于1959年提出而得名。

基本思想：

先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。

该方法实质上是一种分组插入方法。

一般的初次取序列的一半为增量，以后每次减半，直到增量为1。　

假设待排序文件有10个记录，其关键字分别是：

25,19,6,58,34,10,7,98,160,0。

增量序列的取值依次为：

5，2，1

整个希尔排序的算法过程如下如所示：

   

时间性能

Shell排序的时间性能优于直接插入排序

希尔排序的时间性能优于直接插入排序的原因：

①当文件初态基本有序时直接插入排序所需的比较和移动次数均较少。

②当n值较小时，n和n2的差别也较小，即直接插入排序的最好时间复杂度O(n)和最坏时间复杂度0(n2)差别不大。

③在希尔排序开始时增量较大，分组较多，每组的记录数目少，故各组内直接插入较快，后来增量di逐渐缩小，分组数逐渐减少，而各组的记录数目逐渐增多，但由于已经按di-1作为距离排过序，使文件较接近于有序状态，所以新的一趟排序过程也较快。

因此，希尔排序在效率上较直接插人排序有较大的改进。

稳定性

排序前一个序列中,如果出现N个与关键字相同的数据,那么排序后仍然按照原先序列的排列顺序排列,就说这个算法是稳定的,反之就是不稳定的。

希尔排序是不稳定的

public class ShellInsertionSort {

	/**
	 * 希尔排序
	 * 
	 * @param a：待排序数组
	 */
	public static void ShellSort(int[] a,int Index) {
		// 初始集合间隔长度
		int DataLength = (int) Index / 2;
		while (DataLength != 0) // 数列仍可进行分割
		{
			// 对各个集合进行处理
			for (int j = DataLength; j < Index; j++) {
				int Temp = a[j]; // 暂存Data[j]的值,待交换值时用
				int Pointer = j - DataLength; // 计算进行处理的位置
				// 进行集合内数值的比较与交换值
				while (Temp < a[Pointer] && Pointer >= 0 && Pointer <= Index) {
					a[Pointer + DataLength] = a[Pointer];
					// 计算下一个欲进行处理的位置
					Pointer = Pointer - DataLength;
					if (Pointer < 0 || Pointer > Index)
						break;
				}
				// 与最后的数值交换
				a[Pointer + DataLength] = Temp;
			}
			DataLength = DataLength / 2; // 计算下次分割的间隔长度
		}
	}

	public static void main(String[] args) {
		
		int[] a = { 10, 32, 1, 9, 5, 7, 12, 0, 4, 3 };
		
		System.out.print("排序前: ");
		for (int i = 0; i < a.length; i++)
			System.out.printf("%3s ", a[i]);
		System.out.println("");
		
		// 进行排序
		ShellSort(a,a.length); 
		
		// 排序后结果
		System.out.print("排序后: ");
		for (int i = 0; i < a.length; i++)
			System.out.printf("%3s ", a[i]);
		System.out.println("");
	}
}