思路：希尔排序是基于插入排序，针对插入排序中 较小的值 很靠右时，交换次数很多的问题。通过 在元素之间增加间隔，先排序间隔项，最后在执行插入排序（实际上也就是间隔为1的排序）。
例如：增量间隔为4时， 先排序位置再 0、 4、8、12...的数，在排序 1、5、8、13的数，以此类推。结束以后，执行增量间隔为1的排序时，交换的位置最多为2.这样就大大减少了交换开销。
增量间隔的值 并不是固定的。一般来说 h = h*3 + 1 作为间隔序列。例如：对于1000个数据的数组来说，364、121、40、13、4、1。 增量间隔序列的值，就一个要求：最后一个值必然是1
实现：
package com.test; /** * 希尔排序 * @author xurongsheng * @date 2017年4月12日 上午11:42:14 * */ public class ShellSort { private long[] target;//待排序数据 private int length;//数组项个数 public ShellSort(){ } public ShellSort(int maxLength){ target = new long[maxLength]; length = maxLength; } public void setTargetValue(int index,long value){ target[index] = value; } public long getTargetValue(int index){ return target[index]; } public void display(){ System.out.print("A="); for (int i = 0; i < length; i++) { System.out.print(target[i]+" "); } System.out.println(" "); } /** * 希尔排序 * 时间复杂度: O(N(logN)²)~O(N²) * 时间复杂度依赖于 增量间隔的值,一般为N^1.3 * @author xurongsheng * @date 2017年4月12日 上午11:46:49 */ public void shellSort(){ //取最大增量间隔 int h = 1; //间隔增量 while(h <= length/3){ h = h*3 + 1; } while(h>0){ for (int i = h; i < length; i++) { long temp = target[i]; int flag = i; while(flag > (h-1) && target[flag-h] >= temp){ target[flag] = target[flag-h]; flag -= h; } target[flag] = temp; } h = (h-1)/3; //递减增量间隔 } } public static void main(String[] args) { int maxSize = 10000; ShellSort ss = new ShellSort(maxSize); for (int i = 0; i < maxSize; i++) { long n = (long) (Math.random()*1000); ss.setTargetValue(i,n); } ss.display(); long startTime = System.currentTimeMillis(); ss.shellSort(); long endTime = System.currentTimeMillis(); ss.display(); System.out.println("耗时:"+(endTime - startTime)+"ms"); } }
效率：希尔排序的时间复杂度，根据 增量间隔而不同。目前为止还没有定论，大于是在 O（N*(logN)²） 一般都表示为 N^1.3
所以，希尔排序在 最好情况下的时间复杂度为 O（N），最坏情况下的时间复杂度为O（N²），平均为N^1.3
应用场景: 希尔排序对于几千个数据项的中等规模的数组排序表现良好。 其执行效率在最坏情况下和平均情况下的相差不多。所以很多排序优先会考虑希尔排序，效率不行再考虑其他排序。
