希尔排序是插入排序的一种更高效的改进版本。它的作法不是每次一个元素挨一个元素的比较。而是初期选用大跨步（增量较大）间隔比较，使记录跳跃式接近它的排序位置；然后增量缩小；最后增量为 1 ，这样记录移动次数大大减少，提高了排序效率。希尔排序对增量序列的选择没有严格规定。
希尔排序最关键的是选对增量，关于增量的选择，建议参考：希尔排序 中的步长序列。
希尔排序的核心思想是：由一定规则将带排序的长序列切割成多个子序列，子序列进行内部插入排序，如此循环。这个规则就是增量。
package Sort;public class ShellSort {/** * <p> * 是否小于 * </p> * @author zhangjunshuai * @date 2015年4月3日 下午4:14:52 * @param v * @param w * @return */private static boolean less(Comparable v,Comparable w){return v.compareTo(w)<0;}/** * <p> * 交换函数 * </p> * @author zhangjunshuai * @date 2015年4月3日 下午4:14:32 * @param a * @param i * @param j */private static void exch(Comparable[] a,int i ,int j){ Comparable t = a[i]; a[i] = a[j]; a[j] = t; }/** * <p> * 打印输出 * </p> * @author zhangjunshuai * @date 2015年4月3日 下午4:19:03 * @param a */private static void show(Comparable[] a){for(int i = 0; i < a.length; i++){System.out.print(a[i] + " ");}System.out.println();}/** * <p> * 希尔排序 * </p> * @author zhangjunshuai * @date 2015年4月8日 下午8:51:28 * @param a */private static void Shell(Comparable[] a){int N = a.length/2;while(N>0){//增量的判断for(int i=0;i<a.length;i++){//开始循环所有数据int M = (a.length-i-1)/N;//计算i后面还有多少Nfor(int j=1;j<=M;j++){//以插入排序的方式排序增量为N的数for(int h = j;h>0;h–){if(less(a[i+h*N],a[i+(h-1)*N]))exch(a,i+h*N,i+(h-1)*N);elseh=-1;}}}System.out.println("————–增量："+N);show(a);N =N/2;}}public static void main(String[] args) {Integer[] a = {49,38,65,97,76,13,27,49,55,4};Shell(a);}}结果：
第一遍内部对比的组合是（颜色相同的组合）
第二遍内部对比的组合是（颜色相同的组合）
第三遍是对相邻的进行插入的排序
参考：
，穷则思变，差则思勤！没有比人更高的山没有比脚更长的路。
