希尔排序的思路建立在插入排序之上，插入排序可以看我之前写的插入排序的博客。 希尔排序是为了解决插入排序时间复杂度过大的解决方案。我们了解过插入排序，这种算法如果在数组大部分有序的情况下时间复杂度可以到达线性增长。而希尔排序就是先对数组实现h有序，这个h有序意思就是在h个位之间的数组是有序的我们只要不断的缩小这个h那么当h=1时数组就变成了完全有序，而且我们在比较时跳跃h个位，可能会减少比较的次数。
思路： 1.与插入排序相同在仅有一个元素在左时他是有序的 2.这时我们根据h的大小拿取index+h位置的元素进行比较并插入。循环此操作指导末尾，这时数组h有序 3.h=h/2，循环2 操作，直到h==1 4，此时数组完全有序
代码如下：
/** * 希尔排序 * 思路就是对插入排序的基础上设置了一个增量H，每次插入都会移动H。 * 每次结束后都会使数组变为一个增量有序的数组，然后对H缩小，这样重复多次。 * * 由于之前所学选择排序和插入排序的时间复杂度呈现指数上升的，一旦元素过多他的比较次数会异常的多。 * 而希尔排序在面对大亮的元素时会比前两种方法要轻量级的多。 * 从空间占用角度来看这个希尔排序和插入以及选择排序都是一样的并没有太多的多余的空间占用 * 从时间角度来看，希尔排序在大批量的元素处理时会比前两种排序所占有的时间更少 * */ public class suanfa3 { public static void main(String[] args) { int[] ints = new int[100]; Random random = new Random(100); for (int i = 0; i < ints.length; i++) { ints[i] = random.nextInt(100); } soft(ints,13); for (int anInt : ints) { System.out.println(anInt); } } public static void soft(int[] ints,int h){ while (h>=1){ xierSoft(ints,h); h=h/2; } } private static void xierSoft(int[] ints,int h) { int start = 0; while(start<h){ for(int i=start+h;i<ints.length;i+=h){ int key = ints[i]; int index = i-h; while (index>=0&&ints[index]>key){ ints[index+h] = ints[index]; index-=h; } ints[index+h]=key; } start++; } } }