本文正在参加「Java主题月 – Java 刷题打卡」，详情查看 活动链接

1、算法思想

先将要排序的一组数按某个增量d（n/2,n 为要排序数的个数）分成若干组，每组中记录的下标相差 d.对每组中全部元素进行直接插入排序，然后再用一个较小的增量（d/2）对它进行分组，在每组中再进行直接插入排序。当增量减到 1 时，进行直接插入排序后，排序完成。

排序过程：

   待排序序列：39，80，76，41，13，29，50，78，30，11，100，7，41，86

   取步长 d 分别为5，3，1

d=5   39，80，76，41，13，29，50，78，30，11，100，7，41，86

            |——————————-|—————————–|

                    |——————————|——————————|

                            |—————————–|——————————|

                                     |—————————-|——————————|

                                              |——————————-|

各自序列分别为：｛39，29，100｝ ｛80，50，7｝ ｛76，78，41｝ ｛41，30，86｝ ｛13，11｝

对每个自序列进行直接插入排序，顺序调入各个自序列对应排序元素，得到第一趟排序结果：

d=3    29，7，41，30，11，39，50，76，41，13，100，80，78，86

             |—————–|—————–|—————–|——————|

                     |—————-|——————|—————–|——————|

                            |——————|—————–|——————-|

各自序列分别为：｛29，30，50，13，78｝ ｛7，11，76，100，86｝ ｛41，39，41，80｝。对每个自序列进行直接插入排序，顺序调入各个自序列对应排序元素，得到第二趟排序结果：

d=1   13，7，39，29，11，41，30，76，41，50，86，80，78，100

此时，序列基本“有序”，对其直接进行插入排序，得到最终结果：

7，11，13，29，30，39，41，41，50，76，78，80，86，100
 

2、算法代码

import java.util.Arrays;
 
/**
 * 希尔排序：有步长的直接插入排序
 * @author xcbeyond
 * @date 2012-7-8 上午11:27:32
 */
public class ShellSort {
	public static void main(String[] args) {
		int a[] ={13,15,37,89,60,39,12,109,56,72} ;
		shellSort(a);
		
		System.out.println(Arrays.toString(a));
	}
	
	public static void shellSort(int[] array){
		int temp; 
		int d =array.length;//步长
		while(true){ 
			d= d/2; 
		
			for(int i=0;i<d;i++){ 
				for(int j=i+d;j<array.length;j+=d){ 
					int k=j-d; 
					temp=array[j]; 
					for(;k>=0&&temp<array[k];k-=d){ 
						array[k+d]=array[k]; 
					} 
					array[k+d]=temp; 
				} 
			} 
		if(d==1) 
			break; 
 
		}
	}
}
复制代码