算法
希尔排序是对直接插入排序的改进，但其本质上仍然是插入排序，只不过它设置了步长，就变成了跨步长的插入排序。当步长为1时，它就是直接插入排序。
初始时设置步长d为n/2，按照直接插入排序进行，若a[i]<a[i-d]表名a[i]为待排序元素，从后向前与a[i-d],a[i-2d]……比较，若待排序元素小于比较元素，则比较元素向后移位，腾出位置。一趟结束后将待排序元素赋值到空出位置。而后不断更新d=d/2，直到步长为0，排序结束。
例子
仍以序列4,3,1,2,5为例
示例
Codes
package com.fairy.InnerSort;
import java.util.Scanner;
/**
* 希尔排序
* @author Fairy2016
*
*/
public class SheerSort {
public static void sort(int a[], int n) {
int denSity = n / 2;//步长，初始为n/2
int i, j;
while(denSity >= 1) {
for(i = denSity+1; i <= n; i++) {
if(a[i] < a[i-denSity]) {
a[0] = a[i];//非探针，仅作存储
for(j = i-denSity; j > 0 && a[j] > a[0]; j-=denSity) {
a[j+denSity] = a[j];//依然是边比较边移位
}
a[j+denSity] = a[0];//赋值到位置
}
}
denSity /= 2;//更新步长
}
}
public static void Print(int a[], int n) {
for(int i = 1; i <= n; i++) {
System.out.print(a[i]+" ");
}
}
public static void main(String args[]) {
int n;
int a[];
Scanner scanner = new Scanner(System.in);
while(scanner.hasNext()) {
n = scanner.nextInt();
if(n > 0) {
a = new int[n+1];
for(int i=1; i <= n; i++) {
a[i] = scanner.nextInt();
}
sort(a, n);
Print(a, n);
}
}
scanner.close();
}
}
