希尔排序

希尔排序

　　希尔排序是插入排序的升级版，适合数据量比较大的情况下。由于插入排序的特性，我们可以知道，当一个待排序的数组中的数基本有序的时候，采用插入排序的效率较高，但是现实中这种条件比较苛刻。所以没有条件，我们创造条件，希尔排序就是这么来的。怎么创造条件，我们能想到的方法就是让数组“基本有序”, 通过对数组元素进行分组，在每个分组里边利用插入排序进行排序，然后就能得到更加基本有序的序列，重复上述步骤，直到分组最后变为1个的时候，即是数组本身，此时已经排好序了。

代码如下：

public static void HillSort(int [] arr) {
		//gap用来对数据进行分组，对每个分组里的数据进行插入排序
		for(int gap=arr.length/2;gap>0;gap/=2) {
			for(int i=gap;i<arr.length;i+=gap) {
				int temp=arr[i];
				int j;
				for(j=i-gap;j>=0 && temp<arr[j]; j=j-gap) {
					arr[j+gap]=arr[j];
				}
				arr[j+gap]=temp;
			}
		}
	}