希尔排序的思想是使数组中任意间隔为h的的元素都是有序的，这样的数组被称为h有序数组。
1、将无序数组按照若定的增量h分割为若干个子序列，然后对各个子序列进行插入排序。
2、然后再选择一个更小的增量，再将数组分割为多个子序列进行排序。
3、如此类推，最后选择增量为1（即直接插入排序），使最终数组成为有序。
如图上半部分，当h=4时，此系列字符串就由分成四个有序数组(L—M—P—T), (E—H—S—S)，(E—L—O—X)，(A—E—L—R)
希尔排序的实现类似于插入排序，只是使用不同的增量。
1、java部分实现(通过Comparable接口）：
1 public class Shell 2 { 3 private static boolean less(Comparable v, Comparable w) 4 { 5 //compareTo检测v是否小于w,为真返回负，为假返回正，相等返回零 6 return v.compareTo(w) < 0; 7 } 8 9 private static void exch(Comparable[] a, int i, int j) 10 { 11 //交换元素位置 12 Comparable t = a[i]; 13 a[i] = a[j]; 14 a[j] = t; 15 } 16 17 public static void sort(Comparable[] a) 18 { 19 int N = a.length; //数组长度 20 int h = 1; // 增量 21 while (h < N/3) //设定增量h的初始值，为数组长度乘以一个常数因子，最小为1 22 h = 3 * h + 1; //1, 4, 13, 40, 121, 364, 1093 23 while (h >= 1) 24 { //排序 25 for (int i = h; i < N; i++) 26 for (j = i; j >= h && less(a[j], a[j-h]); j -= h) // 分组进行比较， 注意递减量 27 exch(a, j, j - h); 28 h = h / 3; //缩小增量 29 } 30 } 31 }
2、python实现：
1 def Shell(a): 2 h = 1 3 length = len(a) 4 while h < length / 3: 5 h = 3 * h + 1 6 while h >= 1: 7 for i in range(h, length): 8 j = i 9 while j >= h and a[j] < a[j-h]: 10 a[j], a[j-h] = a[j-h], a[j] 11 j = j - h 12 h = h // 3
1、希尔算法的运行时间达不到N2级别（如以上算法的比较次数和N3/2成正比）
2、希尔算法的代码量少，且不会使用额外内存空间。
原文：http://www.cnblogs.com/SlientGuest/p/4904588.html