奔走在算法的大路上（一）排序之希尔排序

希尔排序是插入排序的一种更高效的改进版本。它的作法不是每次一个元素挨一个元素的比较。而是初期选用大跨步（增量较大）间隔比较，使记录跳跃式接近它的排序位置；然后增量缩小；最后增量为 1 ，这样记录移动次数大大减少，提高了排序效率。希尔排序对增量序列的选择没有严格规定。

希尔排序最关键的是选对增量，关于增量的选择，建议参考：http://zh.wikipedia.org/wiki/希尔排序  中的步长序列。

希尔排序的核心思想是：由一定规则将带排序的长序列切割成多个子序列，子序列进行内部插入排序，如此循环。这个规则就是增量。

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后面还有多少N
				for(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);
						else
							h=-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);
	}
	

}

第一遍内部对比的组合是（颜色相同的组合）

第二遍内部对比的组合是（颜色相同的组合）

第三遍是对相邻的进行插入的排序

参考：

http://bubkoo.com/2014/01/15/sort-algorithm/shell-sort/

奔走在算法的大路上（一）排序之希尔排序

原文：http://blog.csdn.net/junshuaizhang/article/details/44947225