主要思想：
基于插入排序，交换不相邻的元素已对数组的局部进行排序，并最终用插入排序将局部有序的数组排序。思想是使数组中任意间隔为h的元素都是有序的，这样的数组称为h有序数组.
Java
public class Shell {
public static void main(String[] args) {
int[] array = new int[]{2, 3, 5, 8, 9, 0, 7, 5, 1, 6, 8, 7, 15};
sort(array);
System.out.println(Arrays.toString(array));
}
private static void sort(int[] array) {
int n = array.length;
int h = 1;
while (h<n/3) h = 3*h +1;
while (h >= 1) {
for (int i = h; i < n; i++) {
for (int j = i; j >= h && (array[j] < array[j - h]); j -= h) {
int temp = array[j];
array[j] = array[j - h];
array[j-h]= temp;
}
}
h /=3;
}
}
}
C
void Shell()
{
for(int incr=3;incr<0;incr--)//增量递减，以增量3，2，1为例
{
for(int L=0;L<(n-1)/incr;L++)//重复分成的每个子列表
{
for(int i=L+incr;i<n;i+=incr)//对每个子列表应用插入排序
{
int temp=arr[i];
int j=i-incr;
while(j>=0&&arr[j]>temp)
{
arr[j+incr]=arr[j];
j-=incr;
}
arr[j+incr]=temp;
}
}
}
}
最好情况时间：O(n)。
最坏情况时间：O(n^2)。
适用于排序小列表，改进了插入排序，减少了比较的次数。是不稳定的排序，因为排序过程中元素可能会前后跳跃。
