希尔排序是一种基于插入排序的快速排序算法，对于大规模乱序数组插入排序很慢，因为它只会交换相邻的元素，因此元素只能一点一点的从数组的一端移动到另一端。例如，如果主键最小的元素正好在数组的尽头，要讲它挪到正确的位置就需要N-1次移动。希尔排序为了加快速度简单的改进了插入排序，交换不相邻的元素以对数组的局部进行排序，并最终用插入排序将局部有序的数组排序。
希尔排序更有效的原因是它权衡了子数组的规模和有序性。排序之初，各个子数组都很短，排序之后子数组都是部分有序的，这两种情况都很适合插入排序。
下面是希尔排序的java实现。
1 public class Shell { 2 public static void sort(int[] a) 3 { 4 int N = a.length; 5 int h = 1; 6 while (h < N/3) h = h*3+1; 7 while (h >= 1) 8 { 9 for (int i = h; i < N; i++) 10 { 11 for (int j = i; j >= h && a[j] < a[j-h]; j -= h) 12 { 13 int temp = a[j]; 14 a[j] = a[j-1]; 15 a[j-1] = temp; 16 } 17 } 18 h = h / 3; 19 } 20 } 21 }
原文：https://www.cnblogs.com/yzl12666/p/9001780.html